충족 가능성 문제: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 Robot: Automated text replacement (-{{토막글|전산학}} +{{토막글|컴퓨터 과학}}) |
전체적으로 다듬고 문단 재정리 |
||
1번째 줄:
'''충족 가능성 문제'''(充足可能性問題, satisfiability problem,
== 기본 정의 ==
논리식은 기본적으로 [[진리값]]을 취하는 논리 변수 <math>x_1, x_2 \
* [[논리합]], <math>(x_1 \lor x_2)
* [[논리곱]], <math>(x_1 \land x_2)
또한, 논리식에서 각각의 <math>x_i</math>, <math>\bar{x_i}</math> 식을 '''리터럴'''(literal)이라고 부른다. 여러 리터럴의 논리합, 즉 <math>x_1 \lor x_2 \lor \cdots \lor x_i</math> 꼴로 이루어진 식을 '''클로저'''(closure), '''절'''이라고 정의한다. 클로저들의 논리곱으로 표현되어 있는 논리식을 [[논리곱 표준형]](CNF)이라고 부른다.
▲* [[부정|논리 부정]] <math>(\bar{x_1}) \dots x_1</math> 이 참이면 거짓, 거짓이면 참
▲* [[논리합]] <math>(x_1 \lor x_2) \dots x_1</math> 이 참이면 <math>x_1\,</math> 거짓이면 <math>x_2\,</math>
▲* [[논리곱]] <math>(x_1 \land x_2) \dots x_1</math>이 참이면 <math>x_2\,</math> 거짓이면<math>x_1\,</math>
== 계산 복잡도 ==
충족 가능성 문제의 [[결정 문제]]는 [[NP-완전]]에 속한다. 이것은 [[스티븐 쿡]]이 증명했으며([[쿡-레빈 정리]]), 이 문제는 NP-완전이라는 것이 증명된 최초의 문제이기도 하다. 또한, 논리식이 [[논리곱 표준형]]으로 이루어진 경우에도 역시 NP-완전에 속한다.
'''3-충족 가능성 문제'''는 '''3-SAT'''이라고도 하며, 논리식을 [[논리곱 표준형|CNF]]로 나타낼 때 한 절에 들어가는 리터럴 개수를 3개 이하로 제한하는 문제이다. 이 문제 역시 [[NP-완전]] 문제이다. 리터럴 개수를 정확히 3개로만 제한하는 문제는 '''EXACT 3-SAT'''이라고 하며, 모든 SAT 문제는 [[다항 시간]]에 3-SAT 또는 EXACT 3-SAT로 [[환산]]될 수 있다.▼
▲'''
== 같이 보기 ==
|