( http://geomblog.blogspot.com/2008/03/joys-of-nae-sat.html 이 글을 보면서 생각난 김에 정리해 두는 중임)

어려운 문제임을 증명할 때, 그 문제를 풀 수 있다면, 3SAT도 풀 수 있음을 보이면 된다. 3SAT은 어려운 문제이므로, 그 증명하고자 하는 문제가 적어도 어려운 3SAT만큼이나 어렵다는 것을 보이는 것이다. 즉, 3SAT의 어떤 문제를 요령껏 바꾸어 어렵다고 증명하고 싶은 문제로 바꾸는 데 성공한다면, 증명하고 싶은 문제를 풀어냄으로서 3SAT을 풀수 있기 때문에, 그 문제는 3SAT보다 쉽지는 않다는 것이다.

3SAT의 정의는 이렇다. 3개의 참 혹은 거짓의 variable이 OR로 연결된 clause이 몇개 있는데 이 모든 clause가 모두 참이 되도록 하는 variable의 조합을 찾아라. 예를 들어 3SAT문제의 instance가 (x+y+z’)(a+b’+c)(x’+b+z) 로 주어졌다면, 여기에 참여한 literal들 x,y,z,a,b,c에 적당한 true, false를 대입함으로서 이 식의 모든 절 clause 세개가 참이 되도록 하는 것이다. 여기서 ‘은 negation이고 +는 logical OR, ()로 구분된 절사이에는 logical AND가 있다. 이 예를 참으로 만드는 조합은 x=true, b=false, z=true, 나머지는 상관없다.

3SAT은 너무 일반적인 형태이기 때문에 때로는 3SAT만큼이나 어려우면서 좀 더 제약된 형태를 이용하는 것이 편리한 경우가 있다. 이어지는 문제들은 그런 것들이다.

Planar 3SAT, 3SAT인데 plane graph로 표시 할 수 있는 것. Graph를 하나 만드는데 그 그래프의 노드는 variable과 clause이다. Variable이 어떤 clause에 참 혹은 거짓으로 참여하고 있다면그 둘 사이에 edge를 둔다. 그리고, clause끼리 연결한 loop을 그린다. 이loop과 graph의 edge가 교차하지 않게 plane에 배열할 수 있으면 그 3SAT은 Planar 3SAT이고, 그것역시 3SAT만큼이나 어렵다. 즉, 누군가Planar 3SAT이 3SAT만큼이나 어렵다고 증명해 두었다는 얘기다. Geometry가 섞인 문제가 어렵다고 증명을 할 때는 그냥 3SAT보다 Planarity가 가미된 것이 편한 경우가 많다.

PN-Planar 3SAT, Planar 3SAT중에서 clause들을 연결한 loop을 기준으로 안쪽에는 참으로 이용된 variable을 바깥쪽에는 거짓으로 이용된 variable을 배치하는 planar graphs가 가능한 것. 즉, 어떤 variable도 참과 거짓 두가지로 쓰이지는 않았다는 얘기.

1IN3SAT, 각 clause의 참인 variable이 하나만 존재하는 것.

Monotone 1IN3SAT, 모든 variable이 참으로만 clause에 참여한 것.

NAE3SAT , Not All Equal 3SAT각 clause의 literal 값이 모두 같지는 않다. 어떤 clause에 있어서 참여한 literal이 모두 거짓일 수는 없기 때문에 이 말은 하나만 참이던지, 두개만 참이어야 한다.

Planar 1IN3SAT, Planar3SAT 이면서 동시에 1IN3SAT인 것. 

Monotone NAE3SAT , Monotone이면서 NAE인 것

MAX 3SAT, 가능한 많은 clause를 참으로 만들자는 문제.

공교롭게도 Planar NAE3SAT은 더 이상 어렵지 않다.