차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
sat [2010-04-11 02:45] lifthrasiir 새로 만듦 |
sat [2011-05-30 18:25] (현재) |
||
|---|---|---|---|
| 줄 5: | 줄 5: | ||
| [[쿡레빈정리]]에 따라서 SAT는 [[NP-완전]]하며, 사실 처음으로 NP-완전임이 증명되었다. 게다가 워낙 일반적인 문제기도 해서 다양한 변종이 알려져 있다. | [[쿡레빈정리]]에 따라서 SAT는 [[NP-완전]]하며, 사실 처음으로 NP-완전임이 증명되었다. 게다가 워낙 일반적인 문제기도 해서 다양한 변종이 알려져 있다. | ||
| - | * 2-SAT는 입력 수식을 2-[[CNF]]로 제한한 것으로, $$O\!(n)$$ 시간에 풀 수 있다. | + | * 2-SAT는 입력 수식을 2-[[CNF]]로 제한한 것으로, $$\mathrm{O}(n)$$ 시간에 풀 수 있다. |
| * 3-SAT는 입력 수식을 3-CNF로 제한한 것으로, 원래 SAT 인스턴스를 3-CNF로 다항시간 안에 바꿀 수 있는 관계로 마찬가지로 NP-완전이다. | * 3-SAT는 입력 수식을 3-CNF로 제한한 것으로, 원래 SAT 인스턴스를 3-CNF로 다항시간 안에 바꿀 수 있는 관계로 마찬가지로 NP-완전이다. | ||
| * NAE-3-SAT("Not all equal")는 3-SAT와 유사하지만 각 항의 변수 중 하나 이상이 참이고 다른 하나 이상이 거짓이어야 한다. 이 문제와, 일반화된 NAE-SAT, 그리고 변수들에 $$\neg$$이 안 붙은 MONOTONE-NAE-3-SAT((원래 버전인 MONOTONE-3-SAT는 물론 졸라 쉽다.)) 모두 NP-완전이다! | * NAE-3-SAT("Not all equal")는 3-SAT와 유사하지만 각 항의 변수 중 하나 이상이 참이고 다른 하나 이상이 거짓이어야 한다. 이 문제와, 일반화된 NAE-SAT, 그리고 변수들에 $$\neg$$이 안 붙은 MONOTONE-NAE-3-SAT((원래 버전인 MONOTONE-3-SAT는 물론 졸라 쉽다.)) 모두 NP-완전이다! | ||
| + | {{tag>전산학}} | ||
저작권자 © 1999–2012 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?