위키백과

충족 가능성 문제: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
시들해봇 (토론 | 기여)
봇
56,507 편집
잔글 Robot: Automated text replacement (-{{토막글|전산학}} +{{토막글|컴퓨터 과학}})
Klutzy (토론 | 기여)
15,566 편집
전체적으로 다듬고 문단 재정리
1번째 줄:
'''충족 가능성 문제'''(充足可能性問題, satisfiability problem, 줄여서 '''SAT''')는 어떠한 [[곱셈 표준형변수]]들로 (CNF)으로 표현된이루어진 논리식이 주어졌을 때, 이그 식에 포함되는 모든 [[변수]]의 값을 참, 거짓으로 정하여 이 식을논리식이 참이 되게되는 할변수값이 수존재하는지를 있는지 여부를 묻는찾는 문제이다. 한국어로는 만족성 문제, 만족도 문제, 만족 문제라고도 한다. 이 문제는 [[스티븐 쿡]]이 최초로 [[NP-완전]]성을 증명한 문제로 유명하고 수많은 학자들이 이 문제에 관심을 가지고 있다. 이 문제는문제, 불린 충족 가능성 문제(boolean satisfiability problem)라고도 한다부른다.
 
== 기본 정의 ==
논리식은 기본적으로 [[진리값]]을 취하는 논리 변수 <math>x_1, x_2 \dotscdots</math>와 및몇몇 [[논리 연산자]]에 결합에 의해 논리식이만들어지는 유한한 길이의 식을 가리킨다. 여기에서 사용되는 연산자는 다음과 이루어진다같다.
* [[부정|논리 부정]], <math>(\bar{x_1})</math>: \dots <math>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\,x_1</math>과 거짓이면<math>x_1\,x_2</math>가 모두 참이면 참, 나머지 경우는 거짓▼
 
또한, 논리식에서 각각의 <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>
 
== 계산 복잡도 ==
* 리터럴 -- 논리 변수 <math>(x_1)\,</math> 또는 그 부정 <math>(\bar{x_1})</math>
* 클로저 -- 리터럴의 논리합 <math>(x_1 \lor \bar{x_2} \lor ...)</math>
 
충족 가능성 문제의 [[결정 문제]]는 [[NP-완전]]에 속한다. 이것은 [[스티븐 쿡]]이 증명했으며([[쿡-레빈 정리]]), 이 문제는 NP-완전이라는 것이 증명된 최초의 문제이기도 하다. 또한, 논리식이 [[논리곱 표준형]]으로 이루어진 경우에도 역시 NP-완전에 속한다.
==변형==
===3-충족 가능성===
'''3-충족 가능성 문제'''는 '''3-SAT'''이라고도 하며, 논리식을 [[논리곱 표준형|CNF]]로 나타낼 때 한 절에 들어가는 리터럴 개수를 3개 이하로 제한하는 문제이다. 이 문제 역시 [[NP-완전]] 문제이다. 리터럴 개수를 정확히 3개로만 제한하는 문제는 '''EXACT 3-SAT'''이라고 하며, 모든 SAT 문제는 [[다항 시간]]에 3-SAT 또는 EXACT 3-SAT로 [[환산]]될 수 있다.▼
 
▲'''3k-충족 가능성 문제'''는, '''3k-SAT'''이라고도는 하며,각 논리식을클로저에 [[논리곱들어있는 리터럴의 갯수가 k개 이하로 구성된 표준형|CNF]]로 나타낼논리식만 때입력으로 받는 문제이다. 예를 들어 3-SAT는 한 절에 들어가는 리터럴 개수를 3개 이하로 제한하는 문제이다. 이 문제3-SAT도 역시마찬가지로 [[NP-완전]] 문제이다. 리터럴 개수를 정확히 3개로만 제한하는 문제는 '''EXACT 3-SAT'''이라고 하며, 모든 SAT 문제는 [[다항 시간]]에 3-SAT 또는 EXACT 3-SAT로 [[환산]]될 수 있다.
===2-충족 가능성===
 
3반면, 2-충족 가능성과 달리SAT, CNF에서 한 절에 들어가는 리터럴 개수가 2개 이하인 문제이다. 이 문제는 [[P (복잡도)|P 문제]]이다에 속한다. 즉, 다항 시간에 풀 수 있다.
 
== 같이 보기 ==
원본 주소 "https://ko.wikipedia.org/wiki/충족_가능성_문제"