차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
sat [2010-04-11 02:46] lifthrasiir spacing이 다르네? 쯥 |
sat [2011-05-30 18:25] (현재) |
||
|---|---|---|---|
| 줄 9: | 줄 9: | ||
| * 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 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?