충족 가능성 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

충족 가능성 문제(SAT)는 주어진 논리식에 대해 변수 값을 할당하여 전체 식을 참으로 만들 수 있는지 판별하는 문제로, 컴퓨터 과학의 다양한 분야에서 중요하게 다루어진다. 이 문제는 NP-완전에 속하며, 논리곱 표준형(CNF) 형태에서도 NP-완전이다. k-충족 가능성 문제(k-SAT)는 CNF 논리식의 각 절에 포함된 리터럴의 개수를 k개 이하로 제한한 문제로, 3-SAT는 NP-완전 문제의 대표적인 예시이다. 2-SAT와 Horn-SAT는 다항 시간 내에 해결 가능하며, XOR-SAT 문제 역시 P에 속한다. SAT는 SMT, QBF 등으로 확장되었으며, 다양한 SAT 해결 알고리즘(DPLL, CDCL, WalkSAT 등)이 개발되어 소프트웨어 검증, 인공 지능, 전자 설계 자동화 등 여러 분야에 응용되고 있다.

더 읽어볼만한 페이지

불 대수 - 드 모르간의 법칙
드 모르간의 법칙은 명제 논리, 술어 논리, 집합론, 부울 대수 등에서 결합 또는 분리의 부정을 각 요소의 부정의 분리 또는 결합으로 표현하는 논리적 원리이다.
불 대수 - 불 논리
불 논리는 0과 1, 참과 거짓의 두 값만으로 논리곱, 논리합, 부정 연산을 통해 명제의 참, 거짓을 판단하고 조작하는 논리 체계로, 라이프니츠의 개념 대수에서 기원하여 조지 불에 의해 체계화되었으며, 섀넌의 스위칭 회로 연구를 통해 디지털 논리 회로 설계의 기초를 다지는 데 기여하며 다양한 분야에서 핵심적인 역할을 수행한다.
전자 설계 자동화 - FPGA
FPGA(Field-Programmable Gate Array)는 사용자가 하드웨어 설계를 변경할 수 있는 집적 회로이며, CPLD에서 파생되어 다양한 제조 기술을 사용하고 디지털 신호 처리, 통신 등 여러 분야에 활용된다.
전자 설계 자동화 - 래더 로직
래더 로직은 PLC 프로그래밍에 사용되는 그래픽 기반 언어로, 릴레이 회로를 연상시키는 접점과 코일을 사용하여 AND, OR, NOT 등의 논리 연산을 구현, 자동화 시스템을 제어한다.
NP-완전 문제 - 지뢰 찾기
지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
NP-완전 문제 - 스도쿠
스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.

충족 가능성 문제
기본 정보
분야	컴퓨터 과학, 수학, 논리학
종류	NP-완전 문제
풀이 방법	백트래킹, DPLL 알고리즘, 확률적 알고리즘
복잡도	NP-완전
역사
최초 제시	스티븐 쿡 (1971년)
관련 문제
연관 문제	회로 만족 문제, 최대 절단 문제, 최대 독립 집합 문제

2. 정의

명제 논리식(부울식)은 변수, AND(결합, ∧), OR(분리, ∨), NOT(부정, ¬) 연산자와 괄호로 구성된다. 변수에 논리값(TRUE, FALSE)을 할당하여 식을 TRUE로 만들 수 있으면 ''충족 가능''하다고 한다. ''부울 만족 문제''(SAT)는 주어진 식이 충족 가능한지 판별하는 결정 문제로, 이론 전산학, 복잡도 이론,^[2]^[3] 알고리즘, 암호학^[4]^[5], 인공 지능 등 컴퓨터 과학 분야에서 중요하다.^[6]

논리식은 참/거짓 값을 갖는 논리 변수( $\textstyle{x_1, x_2 \dots}$ )와 논리 연산자로 구성된다. 논리식의 값을 참으로 만드는 변수 값 조합이 존재하는지를 묻는 것이 충족 가능성 문제이다.

2. 1. 용어

논리식은 기본적으로 진리값을 취하는 논리 변수

x_1, x_2 \cdots

와 몇몇 논리 연산자 결합에 의해 만들어지는 유한한 길이의 식을 가리킨다. 여기에서 사용되는 연산자는 다음과 같다.

논리 부정, $(\overline{x_1})$ : $x_1$ 이 참이면 거짓, 거짓이면 참
논리합, $(x_1 \lor x_2)$ : $x_1$ 이나 $x_2$ 중 적어도 하나가 참이면 참, 나머지 경우는 거짓
논리곱, $(x_1 \land x_2)$ : $x_1$ 과 $x_2$ 가 모두 참이면 참, 나머지 경우는 거짓

또한, 논리식에서 각각의

x_i

,

\overline{x_i}

식을 '''리터럴'''(literal)이라고 부른다. 여러 리터럴의 논리합, 즉

x_1 \lor x_2 \lor \cdots \lor x_i

꼴로 이루어진 식을 '''클로저'''(clause), '''절'''이라고 정의한다. 클로저들의 논리곱으로 표현되어 있는 논리식을 논리곱 표준형(CNF)이라고 부른다.

''명제 논리식''은 ''부울식''이라고도 하며, 변수, 연산자 AND(결합, ∧으로 표시), OR(분리, ∨), NOT(부정, ¬) 및 괄호로 구성된다.^[2]^[3]^[4]^[5]^[6]

3. 계산 복잡도

충족 가능성 문제는 NP-완전 문제의 대표적인 예시이다. 스티븐 쿡이 이 문제를 최초로 증명했으며(쿡-레빈 정리), 논리식이 논리곱 표준형(CNF)으로 이루어진 경우에도 NP-완전에 속한다.

1971년 토론토 대학교의 스티븐 쿠크와 1973년 러시아 과학 아카데미의 레오니트 레빈에 의해 독립적으로 증명된 최초의 NP-완전 문제로 알려져 있다.^[7]^[8] 그 전까지는 NP-완전 문제라는 개념조차 존재하지 않았다. 이 증명은 복잡도 종류 NP에 속하는 모든 결정 문제를 CNF 공식 (때로는 '''CNFSAT'''라고 불림) SAT 문제로 환원할 수 있는 방법을 보여준다. 쿠크 환원의 유용한 속성은 허용되는 답의 수를 보존한다는 것이다. 예를 들어, 주어진 그래프가 3-채색을 갖는지 결정하는 것은 NP의 또 다른 문제인데, 그래프가 17개의 유효한 3-채색을 갖는다면, 쿠크-레빈 환원에 의해 생성된 SAT 공식은 17개의 만족하는 할당을 갖게 된다.

NP-완전성은 최악의 경우 인스턴스의 실행 시간에만 관련된다. 실제 응용 분야에서 발생하는 많은 인스턴스는 훨씬 더 빠르게 해결할 수 있다.

충족 가능성 문제는 NP (비결정적 튜링 머신에 의해 다항 시간 내에 풀 수 있는 문제)이자 NP-난해 문제이며, 이러한 문제의 클래스를 NP-완전 문제라고 한다. 충족 가능성 문제를 다항 시간 내에 변형함으로써, 다양한 NP-완전 문제를 구성할 수 있다.

임의의 논리식으로 구성된 충족 가능성 문제는 NP-완전이지만, 특정 형태를 가진 논리식의 클래스로 제한해도 여전히 NP-완전임이 증명되어 있다.

충족 가능성 문제의 Yes와 No를 반전시키고, 논리식에 부정을 취해 변형하면, 토톨로지 판정 문제가 된다. 토톨로지 판정 문제는 co-NP-완전 문제이다.

3. 1. k-충족 가능성 문제 (k-SAT)

k-충족 가능성 문제(k-SAT)는 각 절에 포함된 리터럴의 개수가 최대 k개로 제한된 논리곱 표준형(CNF) 논리식에 대한 충족 가능성 문제이다.^[10] 예를 들어, 3-SAT는 한 절에 들어가는 리터럴 개수를 3개 이하로 제한하는 문제이다.^[10]

3-SAT는 NP-완전 문제이다.^[10] 리터럴 개수를 정확히 3개로만 제한하는 문제는 EXACT 3-SAT이라고 하며, 모든 SAT 문제는 다항 시간에 3-SAT 또는 EXACT 3-SAT로 환산(Reduction)될 수 있다.^[10] 반면, 2-SAT, 즉 CNF에서 한 절에 들어가는 리터럴 개수가 2개 이하인 문제는 P에 속한다. 즉, 다항 시간에 풀 수 있다.

3-SAT는 카프의 21개 NP-완전 문제 중 하나이며, 다른 문제가 NP-hard임을 증명하는 시작점으로 사용된다.^[10] 이는 3-SAT에서 다른 문제로의 다항 시간 환원을 통해 수행된다.

Schöning (1999)이 제안한 간단한 확률적 알고리즘은 3-SAT 명제의 변수 수가 *n*일 때 (4/3)^*n* 시간으로 실행되며, 3-SAT를 정확하게 결정하는 데 높은 확률로 성공한다.^[12]

지수 시간 가설은 어떠한 알고리즘도 3-SAT (또는 어떤 에 대한 *k*-SAT)를 시간 (즉, *n*에서 근본적으로 지수보다 더 빠르게)에 풀 수 없다고 주장한다.

3-만족성은 각 절이 최대 *k*개의 리터럴을 포함하는 CNF 형식의 명제를 고려할 때, k-만족성 문제 (*k*-SAT, 또는 *k*-CNF-SAT)로 일반화될 수 있다. 하지만, 어떤 *k* ≥ 3에 대해서도 이 문제는 3-SAT보다 쉽지도 않고 SAT보다 어렵지도 않으며, 후자 두 문제는 NP-완전이므로 *k*-SAT도 마찬가지이다.

일부 저자는 *k*-SAT를 정확히 k개의 리터럴을 갖는 CNF 명제로 제한한다. 이것 역시 다른 복잡성 클래스로 이어지지 않는데, 왜냐하면 *j* < *k*개의 리터럴을 갖는 각 절은 고정된 더미 변수를 사용하여 채울 수 있기 때문이다. 모든 절을 패딩한 후, 만족하는 할당으로 이어질 수 있는 것은 뿐임을 보장하기 위해 추가 절^[14]을 추가해야 한다. *k*가 명제 길이에 의존하지 않으므로, 추가 절은 길이를 일정하게 증가시킨다. 같은 이유로, 절에 중복된 리터럴을 허용하는지는 중요하지 않다.

4. SAT의 특수한 경우

결합 정규 형식(CNF) 공식에서 각 절이 최대 세 개의 리터럴로 제한되는 경우를 '''3-SAT''' (3-CNF-SAT 또는 3-만족성 문제)라고 부르며, 이 역시 NP-완전 문제이다.^[10] 예를 들어, $ (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_2 \lor x_3) \land \lnot x_1 $ 은 결합 정규 형식이며, 첫 번째와 세 번째 절은 혼 절이지만 두 번째 절은 혼 절이 아니다. 이 공식은 ''x''₁ = FALSE, ''x''₂ = FALSE, 그리고 ''x''₃를 임의로 선택하여 만족시킬 수 있다.

SAT 문제를 3-SAT로 변환하기 위해, 각 절 $ l_1 \lor \cdots \lor l_n $ 을 $ n-2 $개의 절의 결합으로 바꿀 수 있다.

:$ (l_1 \lor l_2 \lor x_2) \land (\lnot x_2 \lor l_3 \lor x_3) \land (\lnot x_3 \lor l_4 \lor x_4) \land \cdots \land (\lnot x_{n-3} \lor l_{n-2} \lor x_{n-2}) \land (\lnot x_{n-2} \lor l_{n-1} \lor l_n) $

여기서 $ x_2, \cdots, x_{n-2} $는 기존에 없던 새로운 변수들이다. 이렇게 변환된 명제는 원래 명제와 논리적 동치는 아니지만, 동등 만족성을 가진다. 모든 절을 변환한 결과 명제의 길이는 원래 명제의 최대 3배로, 다항식 시간 내에 변환이 가능하다.

3-SAT는 카프의 21개 NP-완전 문제 중 하나이며, 다른 문제가 NP-hard임을 증명하는 데 사용되기도 한다.^[10] 예를 들어, 클리크 문제가 그러한데, ''c''개의 절로 구성된 CNF 명제가 주어지면, 각 리터럴에 대한 꼭짓점을 만들고 서로 다른 절에 속하면서 모순되지 않는^[11] 리터럴 사이에 변을 연결하여 그래프를 구성할 수 있다. 이 그래프는 원래 명제가 만족될 때, 그리고 오직 그 때만 ''c''-클리크를 가진다.

Schöning (1999)은 변수 수가 ''n''인 3-SAT 명제에 대해 $ (4/3)^n $ 시간에 높은 확률로 정답을 찾는 확률적 알고리즘을 제안했다.^[12]

지수 시간 가설에 따르면, 3-SAT (또는 $ k > 2 $ 인 ''k''-SAT)를 $ \exp(o(n)) $ 시간, 즉 ''n''에 대해 지수 시간보다 근본적으로 빠르게 푸는 알고리즘은 존재하지 않는다.

Selman, Mitchell, Levesque (1996)는 무작위로 생성된 3-SAT 명제의 난이도에 대한 경험적 데이터를 제시했는데, DPLL 알고리즘의 재귀 호출 횟수로 측정된 난이도는 절 대 변수 비율이 약 4.26일 때 거의 확실히 만족 가능한 명제에서 거의 확실히 만족 불가능한 명제로 상전이하는 영역을 보였다.^[13]

3-SAT는 각 절이 최대 ''k''개의 리터럴을 포함하는 CNF 형식의 명제를 고려하는 '''k-만족성 문제''' ('''k-SAT''' 또는 '''k-CNF-SAT''')로 일반화될 수 있다. 그러나 $ k \ge 3 $ 인 모든 ''k''에 대해, 이 문제는 3-SAT보다 쉽지도 않고 SAT보다 어렵지도 않으며, 결국 k-SAT도 NP-완전이다.

일부 연구자들은 k-SAT를 '''정확히 k개의 리터럴'''을 갖는 CNF 명제로 제한하기도 한다. 하지만 이 경우에도 $ j < k $개의 리터럴을 갖는 절 $ l_1 \lor \cdots \lor l_j $에 대해 더미 변수를 추가하여 $ l_1 \lor \cdots \lor l_j \lor d_{j+1} \lor \cdots \lor d_k $로 만들고, $ 1 = d_1 = \cdots = d_k = \text{FALSE} $를 보장하기 위해 $ 2^k - 1 $개의 추가 절^[14]을 더하면 되므로 복잡도 클래스는 달라지지 않는다. ''k''가 명제 길이에 의존하지 않으므로 추가 절은 길이를 일정하게 증가시킨다. 마찬가지로, $ \lnot x \lor \lnot y \lor \lnot y $와 같이 절에 '''중복된 리터럴'''을 허용하는지 여부도 중요하지 않다.

4. 1. 2-SAT

2-SAT는 각 절의 리터럴 수가 최대 2개로 제한된 경우의 문제이다. 이 문제는 다항 시간 안에 해결할 수 있으며, 복잡도 클래스 NL에서 완전(complete)하다. 모든 OR 연산을 XOR 연산으로 바꾸면, '''배타적 논리합 2-충족가능성''' 문제가 되는데, 이는 복잡도 클래스 SL = L에 대한 완전 문제이다.

4. 2. Horn-SAT

혼 절(Horn Clause)은 최대 하나의 양의 리터럴을 갖는 절이다.^[17] Horn-SAT는 주어진 혼 절들의 접속(conjunction)의 충족 가능성을 결정하는 문제이다.^[17] 이 문제는 단위 전파 알고리즘의 한 단계로 다항 시간 내에 해결할 수 있으며, 그 결과 Horn 절 집합의 유일한 최소 모델, 즉 참으로 할당된 리터럴 집합을 생성한다.^[17]

Horn-SAT는 P-완전 문제이며, 이는 부울 충족 가능성 문제의 P 버전으로 볼 수 있다.^[17] 또한, 정량화된 Horn 공식의 참/거짓 여부를 결정하는 문제도 다항 시간 내에 해결 가능하다.^[17]

Horn 절은 한 변수가 다른 변수 집합에 의해 함의되는 것을 표현할 수 있어 유용하다.^[17] 예를 들어 ¬''x''₁ ∨ ... ∨ ¬''x''_''n'' ∨ ''y'' 와 같은 절은 ''x''₁ ∧ ... ∧ ''x''_''n'' → ''y'' 로 다시 쓸 수 있는데, 이는 ''x''₁,...,''x''_''n'' 이 모두 참이면 ''y'' 도 참이어야 함을 의미한다.^[17]

Horn 공식의 클래스를 일반화한 것이 재명명 가능한 Horn 공식이다. 이는 일부 변수를 그 부정으로 대체하여 Horn 형태로 바꿀 수 있는 공식 집합을 말한다. 예를 들어 (''x''₁ ∨ ¬''x''₂) ∧ (¬''x''₁ ∨ ''x''₂ ∨ ''x''₃) ∧ ¬''x''₁는 Horn 공식이 아니지만, ''y''₃를 ''x''₃의 부정으로 대체하면 (''x''₁ ∨ ¬''x''₂) ∧ (¬''x''₁ ∨ ''x''₂ ∨ ¬''y''₃) ∧ ¬''x''₁와 같은 Horn 공식으로 재명명할 수 있다. 이러한 변수 대체가 가능한지 여부는 선형 시간 안에 확인할 수 있다. 따라서 재명명 가능한 Horn 공식의 충족 가능성 문제는 P에 속한다.

4. 3. XOR-SAT

각 절이 XOR 연산으로 구성된 XOR-SAT 문제는 다항 시간 안에 해결 가능하다. 이 문제는 가우스 소거법 등을 이용하여 선형 방정식 시스템으로 변환하여 해결할 수 있다.^[18]^[19]

XOR-SAT 공식은 mod 2 선형 방정식 시스템으로 볼 수 있으며, 가우스 소거법을 사용하여 세제곱 시간에 풀 수 있다.^[19] 이는 부울 대수와 부울 링 사이의 관계와 산술 모듈로 2가 유한체를 형성한다는 사실에 기반한다.

예를 들어, 주어진 CNF 공식에 대해 XOR-3-SAT 문제를 풀고, 그 결과를 바탕으로 3-SAT 문제가 풀 수 있는지, 아니면 1-in-3-SAT 문제를 풀 수 없는지 추론할 수 있다.

복잡도 종류 P와 NP가 같지 않다면, XOR-SAT는 SAT와 달리 NP-완전이 아니다.

4. 4. NAE3SAT (Not-All-Equal 3-SAT)

명제 정규형(특히 절당 3개의 리터럴을 갖는 경우)은 SAT 공식의 표준 표현으로 간주되는 경우가 많다. 위에서 보인 바와 같이 일반적인 SAT 문제는 이러한 형태의 공식에 대한 충족 가능성을 결정하는 문제인 3-SAT로 축소된다.

'''Not-all-equal 3-만족성 문제''' ('''NAE3SAT''')는 또 다른 변형이다. 절당 세 개의 리터럴을 갖는 연언 정규형이 주어졌을 때, 이 문제는 변수에 대한 할당이 존재하여 어떤 절에서도 세 리터럴이 모두 동일한 진리값을 갖지 않도록 하는지 여부를 결정하는 것이다. 이 문제는 셰퍼의 이분법 정리에 따라 부정이 허용되지 않더라도 NP-완전 문제이다.^[15]

4. 5. 1-in-3-SAT (Exactly-1 3-SAT)

3-충족가능성 문제의 변형은 '''원-인-쓰리 3-SAT''' ('''1-in-3-SAT''', '''정확히-1 3-SAT'''라고도 함)이다. 절당 세 개의 리터럴을 가진 결합 정규 형식이 주어졌을 때, 문제의 목표는 각 절이 ''정확히'' 하나의 TRUE 리터럴을 갖도록 (따라서 정확히 두 개의 FALSE 리터럴) 변수에 대한 진리 할당이 존재하는지 결정하는 것이다. 반대로, 일반적인 3-SAT는 모든 절이 ''최소한'' 하나의 TRUE 리터럴을 갖도록 요구한다. 공식적으로, 원-인-쓰리 3-SAT 문제는 세 개의 인자를 갖는 연산자 ''R''을 사용하는 일반화된 절로 구성된 일반화된 결합 정규 형식으로 제공되며, 이 연산자는 인자 중 정확히 하나가 TRUE일 때만 TRUE가 된다. 원-인-쓰리 3-SAT 공식의 모든 리터럴이 양수인 경우, 충족가능성 문제는 '''원-인-쓰리 양수 3-SAT'''라고 한다.

원-인-쓰리 3-SAT는 양의 경우와 함께 마이클 R. 게리(Michael R. Garey)와 데이비드 S. 존슨(David S. Johnson)의 표준 참고서인 ''컴퓨터와 난해함: NP-완전성 이론 안내서(Computers and Intractability: A Guide to the Theory of NP-Completeness)''에서 NP-완전 문제 "LO4"로 나열되어 있다. 원-인-쓰리 3-SAT는 토마스 제롬 섀퍼(Thomas Jerome Schaefer)에 의해 섀퍼의 이분법 정리(Schaefer's dichotomy theorem)의 특별한 경우로 NP-완전으로 증명되었다.^[15]

섀퍼는 3-SAT에서 원-인-쓰리 3-SAT로의 쉬운 다항 시간 감소를 허용하는 구성을 제공한다. "(''x'' or ''y'' or ''z'')"를 3CNF 공식의 절이라고 하자. 이 절을 시뮬레이션하고 다른 절에는 사용하지 않도록 6개의 새로운 부울 변수 ''a'', ''b'', ''c'', ''d'', ''e'', ''f''를 추가한다. 그러면 공식 ''R''(''x'',''a'',''d'') ∧ ''R''(''y'',''b'',''d'') ∧ ''R''(''a'',''b'',''e'') ∧ ''R''(''c'',''d'',''f'') ∧ ''R''(''z'',''c'',FALSE)는 적어도 ''x'', ''y'', 또는 ''z'' 중 하나가 TRUE인 경우 새로운 변수의 일부 설정에 의해 충족될 수 있다. 따라서 ''m''개의 절과 ''n''개의 변수를 가진 모든 3-SAT 인스턴스는 5''m''개의 절과 ''n'' + 6''m''개의 변수를 가진 동치충족가능 원-인-쓰리 3-SAT 인스턴스로 변환될 수 있다. 다른 감소는 4개의 새로운 변수와 3개의 절만 포함한다: ''R''(¬''x'',''a'',''b'') ∧ ''R''(''b'',''y'',''c'') ∧ R(''c'',''d'',¬''z'').

'''왼쪽:''' 3-SAT 절 ''x'' ∨ ''y'' ∨ ''z''에 대한 섀퍼의 감소. ''R''의 결과는 인자 중 정확히 하나가 TRUE이면 참(1)이고, 그렇지 않으면 거짓(0)이다. ''x'',''y'',''z''에 대한 값의 모든 8가지 조합이 한 줄에 하나씩 검사된다. 신규 변수 ''a'',...,''f''는 첫 번째 줄을 제외한 모든 줄에서 모든 절을 만족하도록 선택될 수 있으며 (각 ''R''에 정확히 하나의 녹색 인자), 여기서 ''x'' ∨ ''y'' ∨ ''z''는 FALSE이다. '''오른쪽:''' 동일한 속성을 가진 더 간단한 감소.

5. SAT의 확장

SAT 문제는 다양한 형태로 확장되어 연구되고 있다.

Horn-충족 가능성 문제는 주어진 Horn 절들의 접속의 충족 가능성을 결정하는 문제로, 단위 전파 알고리즘으로 다항 시간 내에 해결할 수 있다. P-완전 문제이며, 부울 만족 가능성 문제의 P 버전으로 볼 수 있다. 정량화된 Horn 수식의 진실성을 결정하는 것도 다항 시간 내에 수행할 수 있다.^[17]

Horn 절은 변수 간의 함의를 표현할 수 있어 유용하다. (¬''x''₁ ∨ ... ∨ ¬''x''_''n'' ∨ ''y'')는 (''x''₁ ∧ ... ∧ ''x''_''n'' → ''y'')로 다시 쓸 수 있는데, 이는 ''x''₁,...,''x''_''n''이 모두 TRUE이면 ''y''도 TRUE여야 함을 의미한다.

Horn 수식을 일반화한 재명명 가능한 Horn 수식은 일부 변수를 해당 부정으로 대체하여 Horn 형태로 만들 수 있는 수식 집합이다. 이러한 대체가 존재하는지 확인하는 것은 선형 시간 내에 가능하므로, 재명명 가능한 Horn 수식의 충족 가능성 문제는 P에 속한다.

일반적인 SAT는 공식을 참으로 만드는 변수 할당이 적어도 하나 있는지 묻는다. 이와 관련하여 다양한 변형 문제들이 존재한다.

'''MAJ-SAT'''는 모든 할당의 과반수가 공식을 TRUE로 만드는지 묻는 문제로, PP에 대해 완전하다.
'''#SAT'''는 공식을 만족하는 변수 할당의 개수를 계산하는 문제로, #P-완전이다.
'''UNIQUE SAT'''^[22]는 공식이 정확히 하나의 할당을 갖는지 여부를 결정하는 문제로, US에 대해 완전하다.^[23]
'''UNAMBIGUOUS-SAT''' ('''USAT'''^[24])는 입력이 만족하는 할당이 최대 하나인 공식으로 제한될 때의 만족 가능성 문제이다. Valiant-Vazirani 정리^[25]에 따르면, UNAMBIGUOUS-SAT에 대한 실용적인 알고리즘이 존재한다면 NP의 모든 문제를 쉽게 해결할 수 있다.
'''MAX-SAT''' (최대 만족 가능성 문제)는 모든 할당으로 만족시킬 수 있는 절의 최대 수를 묻는 문제로, FNP의 일반화이다. 효율적인 근사 알고리즘은 존재하지만, 정확하게 해결하기는 NP-어렵다. MAX-SAT는 APX-완전하며, P=NP가 아닌 한 이 문제에 대한 다항 시간 근사 계획 (PTAS)이 없다.
'''WMSAT'''는 단조 부울 공식(부정이 없는 공식)을 만족하는 최소 가중치 할당을 찾는 문제이다. 변수의 가중치는 입력으로 주어지며, 할당의 가중치는 참 변수의 가중치 합이다. 이 문제는 NP-완전이다.^[26]

이 외에도 일계 및 이계 논리, 제약 만족 문제, 0-1 정수 계획법에 대한 만족 가능성 등 다양한 일반화가 존재한다.

충족 가능성 문제는 NP (비결정적 다항 시간) 비결정적 튜링 머신에 의해 다항 시간 내에 풀 수 있는 NP-난해 문제이며, 이러한 문제의 클래스를 NP-완전 문제라고 한다. 충족 가능성 문제를 다항 시간 내에 변형함으로써, 다양한 NP-완전 문제를 구성할 수 있다.

임의의 논리식으로 구성된 충족 가능성 문제는 NP-완전이지만, 특정 형태를 가진 논리식의 클래스로 제한해도 여전히 NP-완전임이 증명되어 있다.

'''CNF-SAT''': 절들의 논리곱으로 구성된 것.
'''3-SAT''': CNF-SAT 중 절 내의 리터럴 수가 최대 3개인 것.

NP 문제의 여집합 문제(결과의 Yes와 No를 반전)를 co-NP 문제라고 한다. 충족 가능성 문제의 Yes와 No를 반전시키고 논리식에 부정을 취해 변형하면 토톨로지 판정 문제가 되는데, 이는 co-NP-완전 문제이다.

논리식의 범위를 [술어 논리식]으로 확장하면 괴델의 불완전성 정리에 의해 충족 가능성 문제는 결정 불가능하다. 술어 논리의 충족 가능성 문제가 결정 가능하다면, 그 방법을 이용하여 자연수론에 의한 그 자체의 모순 없음 증명이 가능하게 되지만, 이는 불완전성 정리에 의해 부정되기 때문이다.

5. 1. SMT (Satisfiability Modulo Theories)

SMT (Satisfiability Modulo Theories)는 SAT를 확장하여 선형 제약 조건, 배열, 비트 벡터 등 다양한 이론을 포함한다.^[20] SMT 솔버는 이러한 확장된 논리식을 효율적으로 처리할 수 있도록 설계되어 있으며, 이러한 확장은 일반적으로 NP-완전성을 유지한다.^[20]

5. 2. QBF (Quantified Boolean Formula)

QBF(Quantified Boolean Formula, 양화 부울 공식)는 전칭 한정사(∀)와 존재 한정사(∃)를 사용하여 변수의 범위를 지정할 수 있도록 SAT를 확장한 것이다. QBF 문제는 PSPACE-완전 문제로 알려져 있다.^[21]

SAT는 (묵시적으로) ∃ 양화사만 사용하는 반면, QBF는 ∀와 ∃ 양화사를 모두 허용한다. 예를 들어,

:''∀x ∀y ∃z (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)''

는 모든 ''x''와 ''y'' 값에 대해 적절한 ''z'' 값을 찾을 수 있기 때문에 참이다. 즉, ''x''와 ''y''가 모두 FALSE이면 ''z''=TRUE이고, 그렇지 않으면 ''z''=FALSE이다.

만약 ∀ 양화사만 허용하면, 항진명제 문제가 되며, 이는 co-NP-완전이다. PSPACE-완전 문제는 NP의 모든 문제보다 엄격하게 어렵다고 널리 알려져 있지만, 아직 증명되지 않았다. 고도로 병렬적인 ''P 시스템''을 사용하면 QBF-SAT 문제를 선형 시간 내에 해결할 수 있다.^[21]

6. SAT 해결 알고리즘

SAT 문제는 NP-완전 문제이므로, 현재까지 알려진 바로는 최악의 경우 지수 시간 복잡도를 갖는 알고리즘만이 존재한다. 그럼에도 불구하고, 2000년대에 SAT 문제 해결을 위한 효율적이고 확장 가능한 알고리즘들이 개발되어, 수만 개의 변수와 수백만 개의 제약 조건(절)을 포함하는 실제 문제 인스턴스들을 자동으로 해결하는 데 큰 발전을 이루었다.^[27]

전자 설계 자동화(EDA) 분야에서 형식적 등가 검증, 모델 검증, 파이프라인 마이크로프로세서의 형식적 검증,^[20] 자동 테스트 패턴 생성, FPGA의 라우팅,^[28] 계획, 스케줄링 문제 등은 SAT 알고리즘이 활용되는 대표적인 예시이다. SAT 솔빙 엔진은 전자 설계 자동화 툴박스의 필수적인 구성 요소로 여겨진다.

현대 SAT 솔버는 데이비스-퍼트남-로게만-러브랜드 알고리즘(DPLL), 충돌 주도 절 학습(CDCL), 확률적 국소 탐색 알고리즘 (예: WalkSAT) 등의 기술을 사용한다. (이 기술들에 대한 자세한 내용은 하위 섹션에서 다룬다.)

최근에는 딥러닝 기술을 활용하여 인스턴스의 만족 가능성을 학습하려는 시도도 이루어지고 있다.^[29]

SAT 솔버는 SAT 솔빙 경연에서 개발되고 비교되며,^[30] 소프트웨어 검증, 인공 지능의 제약 해결, 운용 과학 분야 등에 큰 영향을 미치고 있다.

6. 1. DPLL 알고리즘 (Davis-Putnam-Logemann-Loveland)

데이비스-퍼트남-로게만-러브랜드 알고리즘(DPLL)은 백트래킹을 기반으로 하는 완전 탐색 알고리즘이다. 변수 할당을 단계적으로 확장하며, 충돌이 발생하면 이전 단계로 돌아가 다른 값을 시도한다.^[27]

6. 2. CDCL 알고리즘 (Conflict-Driven Clause Learning)

충돌 주도 절 학습(CDCL) 알고리즘은 데이비스-퍼트남-로게만-러브랜드 알고리즘 (DPLL)을 개선하여 충돌의 원인을 분석하고, 학습된 절(clause)을 추가하여 탐색 공간을 줄인다. 현대 SAT 솔버는 CDCL 알고리즘과 확률적 국소 탐색 알고리즘 (예: WalkSAT)등의 기술을 사용한다.^[27]

6. 3. 확률적 국소 탐색 (Stochastic Local Search)

WalkSAT과 같은 확률적 국소 탐색 알고리즘은 무작위 초기 할당에서 시작하여, 만족되지 않는 절의 리터럴을 무작위로 변경하는 방식으로 해를 찾는다.^[27] 이러한 알고리즘은 타임아웃을 포함하여 해결책을 찾지 못하더라도 합리적인 시간 내에 종료된다. SAT 솔버마다 쉽게 해결하거나 어렵게 해결하는 인스턴스가 다르며, 일부는 만족 불가능성을 증명하는 데 뛰어나고, 다른 일부는 해결책을 찾는 데 뛰어나다.

7. 응용 분야

SAT 솔버는 다양한 분야에서 활용되고 있다.

전자 설계 자동화(EDA) 분야에서 SAT 솔버는 다음과 같은 문제 해결에 사용된다.

형식적 등가 검증
모델 검증
파이프라인 마이크로프로세서의 형식적 검증^[20]
자동 테스트 패턴 생성
FPGA의 라우팅^[28]

또한, SAT 솔버는 다음 분야에도 응용된다.

계획
스케줄링 문제

SAT 솔빙 엔진은 전자 설계 자동화 툴박스의 필수 구성 요소로 간주된다.^[27]

SAT 솔버는 소프트웨어 검증, 인공 지능의 제약 해결, 운용 과학 분야 등에도 상당한 영향을 미치고 있다.

참조

_[1] 서적 2010 IEEE International Test Conference 2010-11
_[2] 서적 Complexity of Computer Computations Plenum 2020-05-07
_[3] 서적 The Design and Analysis of Computer Algorithms Addison-Wesley
_[4] 간행물 Logical Cryptanalysis as a SAT Problem 2000-02-01
_[5] 서적 Theory and Applications of Satisfiability Testing - SAT 2006 Springer 2006
_[6] 간행물 Boolean Satisfiability Solvers and Their Applications in Model Checking
_[7] 서적 Proceedings of the third annual ACM symposium on Theory of computing - STOC '71
_[8] 간행물 Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)
_[9] 문서 The SAT problem for arbitrary formulas is NP-complete, too, since it is easily shown to be in NP, and it cannot be easier than SAT for CNF formulas.
_[10] 문서 i.e. at least as hard as every other problem in NP. A decision problem is NP-complete if and only if it is in NP and is NP-hard.
_[11] 문서 i.e. such that one literal is not the negation of the other
_[12] 서적 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) 1999-10
_[13] 간행물 Generating Hard Satisfiability Problems
_[14] 문서 viz. all [[Canonical form (Boolean algebra)#Maxterms|maxterms]] that can be built with {{math|''d''₁,⋯,''d''_''k''}}, except {{math|''d''₁∨⋯∨''d''_''k''}}
_[15] 회의록 The complexity of satisfiability problems http://www.ccs.neu.e[...]
_[16] 간행물 Selecting and covering colored points 2018-12-11
_[17] 간행물 Resolution for Quantified Boolean Formulas Elsevier
_[18] 문서 Formally, generalized conjunctive normal forms with a ternary Boolean function R are employed, which is TRUE just if 1 or 3 of its arguments is. An input clause with more than 3 literals can be transformed into an equisatisfiable conjunction of clauses á 3 literals similar to [[#3-satisfiability|above]]; i.e. XOR-SAT can be reduced to XOR-3-SAT.
_[19] 서적 The Nature of Computation https://books.google[...] Oxford University Press
_[20] 문서 R. E. Bryant, S. M. German, and M. N. Velev, [http://portal.acm.org/citation.cfm?id=709275 Microprocessor Verification Using Efficient Decision Procedures for a Logic of Equality with Uninterpreted Functions], in Analytic Tableaux and Related Methods, pp. 1–13, 1999.
_[21] 간행물 Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes https://www.research[...]
_[22] 간행물 On the unique satisfiability problem 1982-10-01
_[23] 웹사이트 Complexity Zoo:U - Complexity Zoo https://complexityzo[...] 2019-12-05
_[24] 서적 Theory of Computation Springer 2006
_[25] 간행물 NP is as easy as detecting unique solutions http://www.cs.prince[...]
_[26] 서적 Advances in Information and Computer Security Springer International Publishing 2017
_[27] 서적 Principles and Practice of Constraint Programming – CP 2007
_[28] 간행물 A new FPGA detailed routing approach via search-based Boolean satisfiability http://cs-rutenbar.w[...] 2015-09-04
_[29] arXiv Learning a SAT Solver from Single-Bit Supervision 2019-03-11
_[30] 웹사이트 The international SAT Competitions web page http://www.satcompet[...] 2007-11-15

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com