코디 J. 크리스토퍼(Cody J Christopher)와 찰스 그레튼(Charles Gretton)이 arXiv에 발표한 논문은 대칭 유사 불 제약(symmetric pseudo-Boolean constraints)을 포함하는 불 충족 가능성(Boolean satisfiability) 문제를 풀기 위한 방법으로 병렬 연속 로컬 탐색(CLS, Continuous Local Search)을 탐구한다. 핵심 아이디어는 n개 변수로 구성된 유사 불 충족 가능성 문제를 n차원 초입방체 위에서 미분 가능한 목적함수를 가진 연속 최적화 문제로 완화(relaxation)하는 것이다. 충족 가능한 인스턴스의 경우 이 최적화 문제의 전역 최솟값이 원래 SAT 문제의 충족 배정에 대응한다는 수학적 성질을 활용한다.
연구진은 실험을 통해 세 가지 주요 발견을 도출했다. 첫째, 중복 제약 조건이 수렴을 가속하기보다 오히려 방해할 수 있다는 사실을 확인했다. 둘째, CLS는 부분 배정을 빠르게 완성하는 하이브리드 풀이 도구로서 활용 가능성이 있다. 셋째, 로컬 탐색이 안정적인 해의 품질 분포로 신속하게 수렴한다는 점을 관찰했다. 이 결과들은 현대 가속기 하드웨어, 특히 GPU 환경에서 SAT 문제에 CLS를 실용적으로 적용하는 방향을 제시한다.
SAT 문제는 컴퓨터 과학에서 NP-완전(NP-complete) 문제의 대표 사례로, 논리 회로 설계 검증부터 AI 계획 수립과 제약 만족 문제에 이르기까지 폭넓게 활용된다. 전통적인 DPLL 계열의 완전 탐색 기법과 달리 CLS는 연속 공간에서의 기울기 기반 최적화를 SAT에 도입한다는 점에서 접근 방식이 구별된다. GPU와 같은 대규모 병렬 가속기가 보편화된 환경에서 이 방향의 연구는 현실적 의미를 갖는다.
이번 연구는 병렬 CLS가 단독 풀이보다 하이브리드 전략의 구성 요소로 더 유용할 수 있다는 시각을 제공하며, 대칭 유사 불 제약을 가진 SAT 인스턴스에서 연속 완화 기법의 특성과 한계를 실증적으로 정리한다는 점에서 향후 가속기 기반 조합 최적화 연구에 참고 자료로 활용될 전망이다.
