부울 만족도 문제

논리학과 컴퓨터 과학에서, 부울 만족도 문제(명제 만족도 문제, 약어 AUPTIABILITY, SAT 또는 B-SAT)는 주어진 부울 공식을 만족시키는 해석이 존재하는지 여부를 결정하는 문제이다.즉, 주어진 부울 공식의 변수를 TRUE 또는 FALSE 값으로 일관되게 대체할 수 있는지 여부를 묻습니다.이 경우 공식을 만족할 수 있다고 합니다.한편, 이러한 할당이 존재하지 않는 경우, 공식에 의해 표현되는 함수는 가능한 모든 변수 할당에 대해 FALSE이며 공식은 만족스럽지 않습니다.예를 들어 "a AND NOT b" 공식은 a = TRUE 및 b = FALSE 값을 구할 수 있기 때문에 만족할 수 있다(a AND NOT b).반면 AND NOT a는 만족스럽지 못하다.

SAT는 NP-완전한 것으로 증명된 첫 번째 문제입니다. 쿡-레빈 정리를 참조하십시오.즉, 복잡도 클래스 NP의 모든 문제(자연적 의사결정 및 최적화 문제 포함)는 SAT만큼 해결하기가 어렵다는 것을 의미합니다.각각의 SAT 문제를 효율적으로 해결하는 알려진 알고리즘은 없으며, 일반적으로 그러한 알고리즘은 존재하지 않는다고 믿어진다; 그러나 이 믿음은 수학적으로 증명되지 않았고, SAT가 다항 시간 알고리즘을 가지고 있는지에 대한 문제를 해결하는 것은 com 이론의 유명한 열린 문제인 P 대 NP 문제와 동등하다.퍼팅

그럼에도 불구하고 2007년 현재 경험적 SAT 알고리즘은 수만 개의 변수와 수백만 개의 ^[1]기호로 구성된 공식과 관련된 문제 인스턴스를 해결할 수 있으며, 이는 인공지능, 회로 설계 ^[2]및 자동 정리 증명과 같은 많은 실제 SAT 문제에 충분하다.

정의들

부울식이라고도 불리는 명제 논리식은 변수, 연산자 AND(접합, also로도 표시), OR(분할, ),), NOT(부정, ),) 및 괄호로 구성됩니다.공식은 변수에 적절한 논리값(예: TRUE, FALSE)을 할당함으로써 TRUE가 될 수 있다면 만족할 수 있다고 한다.부울 만족도 문제(SAT)는 공식이 주어지면 만족할 수 있는지 여부를 확인하는 것입니다.이 결정 문제는 이론 컴퓨터 과학, 복잡도 이론,^[3][4] 알고리즘, 암호학^[5][6] 및 인공지능을 ^{[7][additional citation(s) needed]}포함한 많은 컴퓨터 과학 분야에서 매우 중요합니다.

접속 정규형

리터럴은 변수(이 경우 양의 리터럴이라고 함) 또는 변수의 부정(음의 리터럴이라고 함) 중 하나입니다.절은 리터럴(또는 단일 리터럴)의 분리를 말합니다.절이 최대 1개의 양의 리터럴을 포함하는 경우 혼 절이라고 합니다.공식은 절(또는 단일 절)의 조합인 경우 결합 정규 형식(CNF)입니다.예를₁ 들어 x는 양의 리터럴, x는₂ 음의 리터럴, x는₁₂ 절입니다.공식 (x₁₂₁ ∨ x )x (x₂₃ ) x )x₁ 는 접속 정규 형식입니다.첫 번째 절과 세 번째 절은 Horn 절이지만 두 번째 절은 그렇지 않습니다.The formula is satisfiable, by choosing x₁ = FALSE, x₂ = FALSE, and x₃ arbitrarily, since (FALSE ∨ ¬FALSE) ∧ (¬FALSE ∨ FALSE ∨ x₃) ∧ ¬FALSE evaluates to (FALSE ∨ TRUE) ∧ (TRUE ∨ FALSE ∨ x₃) ∧ TRUE, and in turn to TRUE ∧ TRUE ∧ TRUE (i.e. to TRUE).한편, a=TRUE 또는 a=FALSE의 경우 각각 TRUE ∧ TRUE(FALSE) 또는 FALSE ∧ FALSE(다시 FALSE)로 평가되므로 1개의 리터럴의 2개의 절로 이루어진 CNF 공식 a ∧ a a a a a a는 만족스럽지 않다.

SAT 문제의 일부 버전에서는 일반화 정규식 viz.의 개념을 임의의 다수의 일반화 절의 결합으로 정의하는 것이 유용하다.후자는 일부 부울 함수 R 및 (일반) 리터럴_i l에 대한 형식 R(l₁, ...l_n)이다.허용된 부울 함수의 집합이 다르면 다른 버전의 문제가 발생합니다.예를 들어 R(θx, a, b)는 일반화 절이며, R(θx, a, b) r R(b, y, c) r R(c, d, zz)는 일반화 접속 정규 형식이다.이 공식은 다음과 같이 사용됩니다.R은 인수 중 하나가 정확하게 TRUE일 때에만 TRUE인 3진 연산자입니다.

부울 대수의 법칙을 사용하여, 모든 명제 논리식은 동등한 결합 정규 형식으로 변환될 수 있지만, 기하급수적으로 더 길 수 있습니다.예를 들어, (xyy₁₁₂) ( (x₂)y) ... ... (xyy_n)을_n 결합 정규 형식으로 변환하면 다음과 같이 됩니다.

(××××××)_12n

(y_12n … x (

(××××××)_12n

(y₁ y₂ y 、 … x_n x ) 。∧

(××××××××××××××××)_12n

(y₁ x_2n x … … 。

(×××××××××××)_12n

(y₁ ) y₂ … … y_n y );

전자는 2개의 변수의 n개의 결합을 분리한 반면, 후자는 n개의 변수의 2개의 절로 구성됩니다ⁿ.

그러나, Tseytin 변환을 사용하면, 우리는 원래의 명제 논리식의 크기에서 길이가 선형인 동등한 결합 정규식을 찾을 수 있다.

복잡성

1971년 토론토^[8] 대학의 Stephen Cook과 1973년 ^[9]국립과학아카데미의 Leonid Levin이 독립적으로 증명한 것처럼 SAT는 최초로 알려진 NP-완전 문제였다.그 전까지는 NP-완전 문제의 개념이 존재하지도 않았다.증명은 복잡도 클래스 NP의 모든 결정 문제를 CNF 공식(CNFSAT라고도 함)의^{[note 1]} SAT 문제로 줄이는 방법을 보여줍니다.쿡의 감소의 유용한 특성은 수용되는 답변의 수를 보존한다는 것입니다.예를 들어, 주어진 그래프에 3색상이 있는지 여부를 결정하는 것은 NP의 또 다른 문제입니다. 그래프에 17개의 유효한 3색상이 있는 경우, 쿡-레빈 감소에 의해 생성된 SAT 공식에는 17개의 만족스러운 할당이 있습니다.

NP 완전성은 최악의 경우 인스턴스의 실행 시간만 나타냅니다.실제 응용 프로그램에서 발생하는 많은 경우 훨씬 더 빨리 해결할 수 있습니다.아래 SAT를 해결하기 위한 알고리즘을 참조하십시오.

3가지 기능

임의의 공식에 대한 만족도 문제와 마찬가지로 각 절이 최대 3리터까지 제한되는 결합 정규 형식으로 공식의 만족도를 결정하는 것도 NP-완전입니다. 이 문제를 3-SAT, 3CNFSAT 또는 3-만족도라고 합니다.제한되지 않은 SAT 문제를 3-SAT로 줄이려면 각 구₁ l 을 n_n - 2 구의 조합으로 변환합니다.

( l₁ l₂ l x₂ x )

(412x₂ ∨ l₃ xx₃ )

('l₃'x₄' l'x₄)

(412x_{n − 3} ∨ l_{n − 2} xx_{n − 2} )

(138x_{n − 2} ∨ l_{n − 1} l_n l)

여기서₂ x, ,, x는_{n − 2} 다른 곳에서 발생하지 않는 새로운 변수입니다.그 두 공식은 논리적으로 동등하지는 않지만 동등하다.모든 절을 변환하여 얻은 공식은 원래의 공식의 최대 3배이다. 즉, 길이 성장은 ^[10]다항식이다.

3-SAT는 Karp의 21개의 NP-완전 문제 중 하나로, 다른 문제도 ^{[note 2]}NP-난해임을 증명하는 출발점으로 사용됩니다.이것은 3-SAT에서 다른 문제로 다항식 시간을 줄임으로써 이루어집니다.이 방법이 사용된 문제의 예로는 c 절로 구성된 CNF 공식의 경우 대응하는 그래프는 각 리터럴의 정점과 서로 다른 절(cf. picture)의 두 개의^{[note 3]} 모순되지 않는 리터럴 사이의 가장자리로 구성됩니다.그래프에는 공식이 ^[11]만족스러운 경우에만 c-clique가 있습니다.

Schöning(1999)으로 인한 간단한 무작위 알고리즘이 있으며, 여기서 n은 3-SAT ⁿ명제의 변수 수이고, 3-SAT를 ^[12]올바르게 결정할 높은 확률로 성공한다.

지수 시간 가설은 어떤 알고리즘도 3-SAT( k$> 2$의 경우 $k-SAT$를 exp(o(n) 시간(즉, 기본적으로 n의 지수보다 빠름)으로 해결할 수 없다고 주장한다.

Selman, Mitchell 및 Levesque(1996)는 크기 매개변수에 따라 무작위로 생성된 3-SAT 공식의 난이도에 대한 경험적 데이터를 제공한다.난이도는 DPLL ^[13]알고리즘에 의해 실행되는 재귀 콜 수로 측정됩니다.

3-만족도는 CNF의 공식을 최대 k개의 ^{[citation needed]}리터럴을 포함하는 각 절과 함께 고려할 때 k-만족도(k-SAT, k-CNF-SAT)로 일반화할 수 있다.단, 임의의 k ≤ 3에 대해 이 문제는 3-SAT보다 쉬울 수도 없고 SAT보다 어려울 수도 없으며, 나머지 2개는 NP-완전이므로 k-SAT여야 합니다.

일부 저자는 정확히 k ^{[citation needed]}리터럴을 사용하여 k-SAT를 CNF 공식으로 제한한다.j < k 리터럴을 가진 각 절₁ l ∨ ⋯ ⋯ ∨ ∨ ∨ ∨ l d_jjj+1 d에 고정_1k 더미 변수로 패딩할 수 있기 때문에 이것은 다른 복잡도 클래스로 이어지지 않습니다. 모든 절을 패딩한 후 d = d_k = false만 할당할₁ 수 있도록 하기 위해 2-1^k 추가^{[note 4]} 절을 추가해야 합니다.k는 공식 길이에 의존하지 않기 때문에 추가 절에 따라 길이가 계속 증가합니다.같은 이유로, "x "y "와 같이 구에서 중복 리터럴이 허용되는지 여부는 중요하지 않습니다.

SAT의 특수한 경우

접속 정규형

접속 정규형(특히 절당 3리터)은 종종 SAT 공식의 표준 표현으로 간주됩니다.위와 같이 일반적인 SAT 문제는 3-SAT로 감소하는데, 이는 이 형태의 공식에 대한 만족도를 결정하는 문제이다.

분리정규형

SAT는 공식들이 분리 정규 형식의 공식들로 제한된다면, 즉, 리터럴의 결합의 분리인 경우 사소한 것이다.이러한 공식은 그 접속사 중 적어도 하나가 만족할 수 있는 경우에만 만족할 수 있으며, 어떤 변수 x에 대해 x와 NOT x를 모두 포함하지 않는 경우에만 만족할 수 있다.이것은 선형 시간으로 확인할 수 있습니다.또한 모든 변수가 모든 연결에서 정확히 한 번씩 나타나는 완전한 분리 정규 형식으로 제한되는 경우 일정한 시간 내에 확인할 수 있습니다(각 연결은 하나의 할당 만족을 나타냅니다).그러나 일반적인 SAT 문제를 분리 정규 형식으로 변환하려면 기하급수적인 시간과 공간이 필요할 수 있습니다. 예를 들어, 연결 정규 형식의 경우 위의 지수 확대 예에서 " the"와 """를 교환합니다.

정확히 1 - 3가지 만족도

3-만족도 문제의 변형으로는 1-in-3-SAT(일명 1-in-3-SAT 및 정확히-1 3-SAT라고도 함)가 있습니다.절마다 3개의 리터럴을 갖는 접속사 정규형이 주어진 경우, 문제는 각 절이 정확히 1개의 TRUE 리터럴(따라서 정확히 2개의 FALSE 리터럴)을 가지도록 변수에 진실 할당이 존재하는지 확인하는 것입니다.반면 일반 3-SAT에서는 모든 구에 적어도1개의 TRUE 리터럴이 필요합니다.형식적으로, 모든 일반화 절이 TRUE인 3진 연산자 R을 사용하는 일반화된 접속사 정규 형식으로 3-SAT 문제가 주어집니다.3중 1의 3-SAT 공식의 모든 리터럴이 양수일 때, 만족도 문제는 3중 1의 3-SAT라고 불립니다.

3-SAT 3분의 1은 긍정적인 경우와 함께 표준 참고 자료인 컴퓨터와 난해성: Michael R.의 NP-완전성 이론 가이드에서 NP-완전성 문제 "LO4"로 나열되어 있습니다. 개리와 데이비드 S. 존슨입니다.토마스 제롬 셰퍼에 의해 3-SAT가 NP-완전이라는 것이 증명되었다. 셰퍼의 이분법 정리의 특별한 경우로서, 셰퍼는 부울 만족도를 특정 방식으로 일반화하는 문제는 모두 클래스 P이거나 ^[14]NP-완전이라고 주장한다.

Shaefer는 3-SAT에서 3-in-3-SAT로 다항식 시간을 쉽게 줄일 수 있는 구조를 제공한다.한3CNF 공식으로"(x나 또는 zy)" 수 있는 조항자., 이 조항이며, 다른어떤 모의 실험하기 위해 사용할 6개 신선한 boolean 변수는, b, c, d, e와 f를 넣으세요.신선한 변수의 설정 만일 최소한 하나의 x, y, 또는 z사실에 의해 그리고 그 공식 R(x,a,d)∧ R(y,b,d)∧ R(a,b,e)∧ R(c,d,f)∧ R(z,c,FALSE)은 만족시킬 수 있는 참조 사진( 떠났다).따라서 m조항과 n변수에 어떤 3-SAT 인스턴스equisatisfiable 생활 3-SAT 인스턴스에 전체 조항과n+6m 변수로 변환할 수 있다.[15]또 다른 감소, 그림(바로)참조하십시오 4개밖에 없는 신선한 변수와 3절 R(¬x,a,b)∧ R(b,y,c)∧ R(c,d,¬z)을 포함한다.

전혀 같지 않은 3가지 만족도

또 다른 변형으로는 모든 것이 동일하지 않은 3-만족도 문제(NAE3SAT라고도 함)가 있습니다.절당 3리터씩의 접속사 정규형이 주어졌을 때, 문제는 변수에 대한 할당이 존재하는지 여부이며, 어떤 절에서도 3리터 모두 동일한 진실 값을 가지지 않는지를 결정하는 것이다.이 문제도 셰퍼의 이분법 ^[14]정리에 의해 부정 기호가 인정되지 않더라도 NP-완전이다.

선형 SAT

3-SAT 공식은 각 절(리터럴 세트로 표시됨)이 최대 1개의 다른 절과 교차하고, 또한 2개의 절이 교차하는 경우에는 정확히 1개의 리터럴이 공통되는 경우 선형 SAT(Linear SAT)입니다.LSAT 공식은 회선상의 불연속 반폐쇄 구간의 집합으로 나타낼 수 있습니다.LSAT 공식이 충족되는지 여부를 결정하는 것은 NP-완전입니다.^[16]

2개의 호환성

절의 리터럴 수가 최대 2개로 제한되면 SAT가 더 쉬워집니다. 이 경우 문제를 2-SAT라고 합니다.이 문제는 다항식 시간 내에 해결할 수 있으며, 실제로 복잡도 클래스 NL에 대해 완료됩니다. 추가로 리터럴의 모든 OR 연산을 XOR 연산으로 변경하면 그 결과를 배타적 또는 2-불가능성이라고 하며, 이는 복잡도 클래스 SL = L에 대해 완전한 문제입니다.

경음기 만족도

주어진 혼 절의 결합에 대한 만족도를 결정하는 문제를 혼-만족도 또는 혼-SAT라고 합니다.단위 전파 알고리즘의 한 단계로 다항 시간에 해결할 수 있습니다. 단위 전파 알고리즘은 경음기 절 세트의 단일 최소 모델(TRUE에 할당된 리터럴 집합 포함)을 생성합니다.경음기 만족도는 P-complete입니다.P 버전의 부울 만족도 문제로 볼 수 있습니다.또한 정량화된 Horn 공식의 진위 판정은 다항식 시간에 할 수 있다.^[17]

경음기 절은 다른 변수 집합에서 한 변수를 암시하는 의미를 표현할 수 있기 때문에 관심이 있습니다.실제로 이러한 조항 중 하나인 'x₁'는 ...이다.'x_n' y는 'x'로 고쳐₁ 쓸 수 있습니다.θ_n x → y, 즉_n x₁,...x가 모두 TRUE이면 y도 TRUE여야 합니다.

호른 공식의 일반화는 이름 변경 가능한 호른 공식으로, 일부 변수를 각각의 부정으로 대체함으로써 호른 형태로 배치할 수 있습니다.예를₃ 들어 (x₁₁ ∨x₂) ( ( xx xx₂ x xx₃) (x는₁ 혼 공식은 아니지만 x의 부정으로서 y를 도입함으로써₃ 혼 공식(x₁ xx₂) ( (x₁ xx)로 이름을 바꿀₁ 수 있다₂₃.반대로 (x₁₁ xx₂ ∨x₃ )x) (x )x )x₂₃)의₁ 이름을 바꾸면 Horn 공식으로 이어지지 않습니다.이러한 치환의 존재여부를 선형시간에 확인할 수 있으므로, 이러한 공식의 만족도는 우선 이 치환을 수행한 후 Horn 공식의 만족도를 확인함으로써 해결할 수 있기 때문에 P에 있다.

2절의 공식은 첫 번째(hor) 및 두 번째(vert)절의 TRUE-literal 카운트에 따라 불만족(빨간색), 3가지(녹색), xor-3-만족(파란색) 또는/또는 1가지-in-3-만족(노란색)일 수 있다.

XOR 만족도

XOR-SAT 예시 해결 가우스 제거에 의해
주어진 공식 ("""는 XOR, red 절은 옵션) (a'c'd) (b'c'd) (a'b'd) (a'b'c) (a'b'c)
방정식 시스템 ("1"은 TRUE, "0"은 FALSE) 각 절은 하나의 방정식으로 이어진다. a ⊕ c ⊕ d = 1 b ⊕ ¬ c ⊕ d = 1 a ⊕ b ⊕ ¬ d = 1 a ⊕ ¬ b ⊕ ¬ c = 1 ¬ a ⊕ b ⊕ c ≃ 1
정규화 방정식 시스템 부울링 속성 사용(booleanx=1grapx, xgrapx=0) a ⊕ c ⊕ d = 1 b ⊕ c ⊕ d = 0 a ⊕ b ⊕ d = 0 a ⊕ b ⊕ c = 1 a ⊕ b ⊕ c § 0 (빨간색 방정식이 존재할 경우, 이는 다음과 같다. 마지막 검정색이라 시스템을 해결할 수 없습니다. 따라서 가우스의 알고리즘은 검정색 방정식에만 사용됩니다.)
연관 계수 행렬 a b c d 선 1 0 1 1 1 A 0 1 1 1 0 B 1 1 0 1 0 C 1 1 1 0 1 D
echelon 형식으로 변환 a b c d 작동 1 0 1 1 1 A 1 1 0 1 0 C 1 1 1 0 1 D 0 1 1 1 0 B(스왑 완료) 1 0 1 1 1 A 0 1 1 0 1 E = CΩA 0 1 0 1 0 F = DΩA 0 1 1 1 0 B 1 0 1 1 1 A 0 1 1 0 1 E 0 0 1 1 1 G = FΩE 0 0 0 1 1 H = BΩE
대각선 형태로 변환 a b c d 작동 1 0 1 0 0 I = AhH 0 1 1 0 1 E 0 0 1 0 0 J = GΩH 0 0 0 1 1 H 1 0 0 0 0 K = IjJ 0 1 0 0 1 L = E440J 0 0 1 0 0 J 0 0 0 1 1 H
솔루션: 빨간색 절이 있는 경우: 해결할 수 없다 기타: a = 0 = FALSE b = 1 = TRUE c = 0 = FALSE d = 1 = TRUE 그 결과: R(a,c,d) r R(b,cc,d) r R(a,b,dd) r R(a,bb,cc) r R(aa,b,)c) 1-in-3-compatible이 아닙니다. 한편 (a' c' d) (b' c' d) (a' b' d) (a' b' d) (a' b' b' d) 는 a=c=FALSE 및 b=d=TRUE와 3-불규칙합니다.

또 다른 특수한 경우는 각 절에 (일반) OR ^{[note 5]}연산자가 아닌 XOR(배타적) 또는 XOR(배타적)이 포함되어 있는 문제의 클래스입니다.XOR-SAT 공식은 선형 방정식 mod 2의 시스템으로도 볼 수 있고, 가우스 ^[18]제거에 의해 입방 시간 내에 풀 수 있기 때문에, 예를 들어 상자를 참조하십시오.이 리캐스트는 부울 대수와 부울링 사이의 친족관계와 산술 모듈로 2가 유한장을 형성한다는 사실에 기초한다.XOR b XOR c는 {a,b,c}의 멤버가 정확히 1개 또는 3개 True인 경우에만 TRUE로 평가되므로 특정 CNF 공식에 대한 1-in-3-SAT 문제의 각 해법도 XOR-3-SAT 문제의 해법이며, 이에 따라 XOR-3-SAT의 각 해법도 TRUE로 평가됩니다.그 결과 CNF 식별로 식에 의해 정의된 XOR-3-SAT 문제를 해결할 수 있으며, 그 결과에 따라 3-SAT 문제가 해결 가능한지 1-in-3-SAT 문제가 해결 불가능한지를 추론할 수 있다.

복잡도 등급 P와 NP가 동일하지 않은 경우, SAT와 달리 2-, Horn-, XOR-만족도는 NP-완전이다.

셰퍼의 이분법 정리

위의 제약사항(CNF, 2CNF, 3CNF, Horn, XOR-SAT)에서는 고려된 공식은 보조 공식의 결합으로 한정되어 있습니다.각 제한사항은 모든 보조 공식에 대해 특정 형식을 명시합니다. 예를 들어 2CNF에서는 이진 절만 보조 공식으로 지정할 수 있습니다.

섀퍼의 이분법 정리는 이러한 부공식을 형성하는 데 사용될 수 있는 부울 함수에 대한 제한에 대해, 대응하는 만족도 문제는 P 또는 NP-완전이라는 것을 말한다.2CNF, Horn, XOR-SAT 공식의 P 만족도는 이 ^[14]정리의 특별한 경우이다.

다음 표에는 일반적인 SAT 변형 모델이 요약되어 있습니다.

코드	이름.	제약 사항	요구 사항들	학급
3SAT	3가지 기능	각 절에는 3리터가 포함되어 있습니다.	하나 이상의 리터럴이 참이어야 합니다.	NPC
2SAT	2개의 호환성	각 절에는 2 리터럴이 포함되어 있습니다.	하나 이상의 리터럴이 참이어야 합니다.	P
1-in-3-SAT	정확히 1 3-SAT	각 절에는 3리터가 포함되어 있습니다.	정확히 하나의 리터럴이 참이어야 합니다.	NPC
1-in-3-SAT+	정확히 1 플러스 3-SAT	각 절에는 3개의 양의 리터럴이 포함되어 있습니다.	정확히 하나의 리터럴이 참이어야 합니다.	NPC
NAE3SAT	전혀 같지 않은 3가지 만족도	각 절에는 3리터가 포함되어 있습니다.	하나 또는 두 리터럴이 참이어야 합니다.	NPC
NAE3SAT+	모든 것이 동일하지 않은 3-SAT	각 절에는 3개의 양의 리터럴이 포함되어 있습니다.	하나 또는 두 리터럴이 참이어야 합니다.	NPC
PL-SAT	평면 SAT	발생 그래프(절대 변수 그래프)는 평면입니다.	하나 이상의 리터럴이 참이어야 합니다.	NPC
L3SAT	선형 3-SAT	각 절은 최대 1개의 다른 절과 교차하며 교차점은 정확히 1개의 리터럴입니다.	하나 이상의 리터럴이 참이어야 합니다.	NPC
경음기	경음기 만족도	혼 절(최대 1개의 양의 리터럴).	하나 이상의 리터럴이 참이어야 합니다.	P
XOR-SAT	Xor 만족도	각 절에는 OR이 아닌 XOR 연산이 포함됩니다.	모든 리터럴의 XOR은 참이어야 합니다.	P

SAT의 확장

2003년 이후 큰 인기를 얻고 있는 확장은 선형 제약, 배열, 모두 다른 제약, 해석되지 않은 ^[19]함수 등으로 CNF 공식을 풍부하게 만들 수 있는 만족도 모듈로 이론(SMT)이다.이러한 확장은 일반적으로 NP-완전한 상태로 유지되지만, 현재는 이러한 많은 종류의 제약을 처리할 수 있는 매우 효율적인 솔버를 사용할 수 있습니다.

만족도 문제는 "for all"())과 "there exist"()) 양식이 모두 부울 변수와 결합할 수 있는 경우 더욱 어려워집니다.An example of such an expression would be ∀x ∀y ∃z (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z); it is valid, since for all values of x and y, an appropriate value of z can be found, viz. z=TRUE if both x and y are FALSE, and z=FALSE else.SAT 자체(정확히)는 quant의 수량만 사용합니다.대신 δ의 정량자만 허용하면 이른바 동질성 문제가 얻어지며, 이는 co-NP-완전이다.두 개의 정량자를 모두 사용할 수 있는 경우 이 문제는 Quantified Boolean Formula Problem(QBF; 정량화된 부울식 문제)라고 불리며 PSPACE-complete로 나타낼 수 있습니다.PSPACE-완전 문제는 NP의 어떤 문제보다 엄격히 어렵다고 널리 알려져 있지만, 이는 아직 증명되지 않았습니다.고도로 병렬화된 P 시스템을 사용하면 QBF-SAT 문제를 선형 시간 ^[20]내에 해결할 수 있습니다.

일반 SAT에서는 공식을 참으로 만드는 변수 할당이 하나 이상 있는지 여부를 확인합니다.다양한 변형에서 이러한 할당의 수를 처리합니다.

• MAJ-SAT는 모든 과제의 대부분이 공식을 참으로 만드는지 여부를 묻습니다.확률론적 등급인 PP에 대해 완전한 것으로 알려져 있다.
• #SAT는 변수 할당이 몇 개나 공식을 만족하는지를 세는 문제이며, 결정 문제가 아니라 #P-완전입니다.
• UNIQURE^[21] SAT는 공식에 정확히 하나의 할당이 있는지 확인하는 문제입니다.그것은 정확히 하나의 비결정론적 수용 경로가 있을 때 받아들이고 그렇지 않으면 거부하는 비결정론적 다항식 시간 튜링 기계에 의해 해결 가능한 문제를 설명하는 복잡도 클래스인 ^[22]US에 대해 완전하다.
• UNMARCUSUES-SAT는 입력이 최대 1개의 만족스러운 할당을 가진 공식으로 제한될 때 만족도 문제에 붙여진 이름입니다.이 문제는 ^[23]USAT라고도 불린다.UNMICUSURE-SAT를 위한 해결 알고리즘은 몇 가지 만족스러운 할당을 가진 공식에 대해 무한 루프를 포함한 모든 동작을 나타낼 수 있다.이 문제는 쉬워 보이지만 Valiant와 Vazirani는 이를 해결하기 위한 실용적인(즉, 무작위 다항식 시간) 알고리즘이 있다면 NP의 모든 문제를 똑같이 쉽게 해결할 수 있다는 것을 보여주었다^[24].
• 최대 만족도 문제인 MAX-SAT는 SAT의 FNP 일반화이다.할당에 의해 충족될 수 있는 최대 절 수를 요구합니다.효율적인 근사 알고리즘이 있지만 NP-정확히 해결하기가 어렵습니다.더 나쁜 것은 P=NP가 아닌 한 이 문제에 대한 다항식 시간 근사 체계(PTAS)가 없다는 것을 의미하는 APX-완전이라는 점이다.
• WMSAT는 단조 부울 공식(즉, 부정 없는 공식)을 만족하는 최소 가중치 할당을 찾는 문제이다.명제 변수의 가중치는 문제의 입력에 주어진다.할당의 가중치는 참 변수의 가중치의 합입니다.이 문제는 NP-완전입니다(의 제1절 참조).

다른 일반화에는 1차 및 2차 로직의 만족도, 제약 조건 만족 문제, 0-1 정수 프로그래밍이 포함된다.

만족스러운 과제 찾기

SAT는 의사결정 문제이지만, 만족스러운 과제를 찾는 검색 문제는 SAT로 감소합니다.즉, SAT 인스턴스가 해결 가능한 경우 올바르게 응답하는 각 알고리즘을 사용하여 만족스러운 할당을 찾을 수 있습니다.먼저 주어진 공식 δ에 대한 질문을 합니다.만약 "아니오"라고 대답한다면, 공식은 만족스럽지 못한 것입니다.그렇지 않으면 부분적으로 인스턴스화된 공식 δ{x₁=TRUE}, 즉 첫 번째 변수₁ x가 TRUE로 대체된 δ에 대해 질문을 하고 그에 따라 단순화한다.대답이 "예"이면 x₁=TRUE이고, 그렇지₁ 않으면 x=FALSE입니다. 다른 변수의 값은 같은 방법으로 나중에 찾을 수 있습니다.총 n+1의 알고리즘 실행이 필요합니다.여기서 n은 δ 내의 고유 변수 수입니다.

이 특성은 복잡도 이론의 여러 이론에서 사용됩니다.

NP p P/poly ph PH = σ₂ (Karp-Lipton 정리)

NP ⊆ BPP np NP = RP

P = NP fp FP = FNP

SAT를 해결하기 위한 알고리즘

SAT 문제는 NP-complete이기 때문에 지수적으로 최악의 경우 복잡성을 갖는 알고리즘만 알려져 있습니다.그럼에도 불구하고, SAT를 위한 효율적이고 확장 가능한 알고리즘은 2000년대에 개발되었으며 수만 개의 변수와 수백만 개의 제약 조건(예: 조항)^[1]과 관련된 문제 인스턴스를 자동으로 해결하는 능력의 극적인 발전에 기여했다.전자설계자동화(EDA)에서 이러한 문제의 예로는 정식 등가검사, 모델체크, 파이프라인 마이크로프로세서의 ^[19]정식검증, 자동테스트 패턴 생성, FPGA ^[26]라우팅, 계획 및 스케줄링 문제 등이 있습니다.SAT 해결 엔진은 또한 전자 설계 자동화 도구 상자에서 필수적인 구성 요소로 간주됩니다.

현대의 SAT 해결사가 사용하는 주요 기술에는 데이비스(Davis)가 있습니다.Putnam-Logemann-Loveland 알고리즘(또는 DPLL), Conflict-Driven Clause Learning(CDCL) 및 WalkSAT와 같은 확률적 로컬 검색 알고리즘.거의 모든 SAT 솔버에는 타임아웃이 포함되어 있기 때문에 해결책을 찾지 못하더라도 합리적인 시간 내에 종료됩니다.SAT 해결사마다 다른 인스턴스가 쉽거나 어렵거나 만족스럽지 못함을 입증하는 데 탁월하거나 해결책을 찾는 데 탁월하다는 것을 알게 됩니다.

SAT 해결사는 SAT 해결 ^[27]대회에서 개발되고 비교됩니다.최신 SAT 솔버는 소프트웨어 검증, 인공지능 제약 해결, 운영 연구 등에도 큰 영향을 미치고 있습니다.

「 」를 참조해 주세요.

• 만족할 수 없는 코어
• 만족도 모듈로 이론
• SAT 카운트
• 평면 SAT
• 카를로프-즈윅 알고리즘
• 회로 만족도

메모들

외부 링크

• SAT 게임: 부울 만족도 문제를 직접 해결해 보십시오.
• 국제 SAT 콩쿠르 웹사이트
• 만족도 테스트 이론 및 적용에 관한 국제 회의
• 만족도, 부울 모델링 및 계산에 관한 저널
• SAT Live, 만족도 문제에 대한 연구를 위한 종합 웹사이트
• MaxSAT 솔버의 연간 평가

레퍼런스

발행일별 추가 참고 자료:

---

이 기사에는 ACM SIGDA 전자 뉴스레터의 칼럼에 있는 Professor가 게재하고 있습니다. Karem Sakalla 오리지널 텍스트는 이쪽