arXiv:2605.09347v2 cs.AI

Dsat: 이산 논리를 위한 네이티브 SAT 솔버

Dsat: A Native SAT Solver for Discrete Logic

Yaofang Zhang, Ken Zhou, Adnan Darwiche

제출 2026-11-17

한국어 초록

이산 변수는 확률적 추론, 계획, 설명 가능한 AI 등 많은 응용에서 흔히 나타난다. 이러한 응용에 기호적 추론 기법을 적용할 때, 이산 변수를 다루는 표준적인 방법은 SAT 솔버와 같은 불리언 계산 장치를 사용할 수 있도록 이를 불리언 변수로 이진화하는 것이다. 그러나 이 기법은 계산적, 의미론적 어려움에 직면할 수 있다. 본 연구에서는 변수가 임의의 값을 취할 수 있는 불리언 논리의 직접적 확장인 이산 논리를 위한 네이티브 SAT 솔버를 개발한다. 제안하는 솔버는 불리언 SAT 솔버와 유사한 설계를 가지며 단위 분해와 절 학습 같은 요소를 갖추되, 이들이 이산 변수 위에서 네이티브로 동작한다. 개발한 SAT 솔버의 장점은 이산 CNF에 적용한 CSP 솔버, 이진화된 CNF에 적용한 불리언 SAT 솔버, 그리고 일부 하이브리드 솔버와 경험적으로 비교하여 보인다.

원문 초록

Discrete variables are common in many applications, such as probabilistic reasoning, planning and explainable AI. When symbolic reasoning techniques are brought in to bear on these applications, a standard technique for handling discrete variables is to binarize them into Boolean variables to allow the use of Boolean computational machinery such as SAT solvers. This technique can face both computational and semantical challenges though. In this work, we develop a native SAT solver for discrete logic, which is a direct extension of Boolean logic in which variables can take arbitrary values. Our proposed solver has a similar design to Boolean SAT solvers, with ingredients such as unit resolution and clause learning but ones that operate natively on discrete variables. We illustrate the merits of the developed SAT solver by comparing it empirically to CSP solvers applied to discrete CNFs, to Boolean SAT solver applied to binarized CNFs, and to some hybrid solvers.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2605.09347v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.