| NP 완전 문제 | 여러 가지 NP 완전문제 | NP-완전성과 변환성 |

여러 가지 NP 완전 문제

■  CNF 만족성(Conjunctive Normal Form Satisfiability) 문제

   - CNF로 주어진 논리식의 리터럴들에 참 또는 거짓 값을 적절히 지정하여 전체 논리식의 값을 참으로 만들 수가 있는 지를 판정하는 문제

   - 리터럴은 논리변수 xi 또는 그 부정형 를 말한다. CNF형은 여러 개의 절이 ∧(AND)로 연결된 논리식이다. 각 절은 ∨(OR)로 연결된 리터럴의 시퀀스다.

  - 예제
--------------------------------------------------------------------------------

        아래 CNF 논리식에서 논리변수 xi의 값을 적절히 정하여 이 식이 참이 되도록 할 수 있는가?

        ( x1∨ x3 ∨ x5) ∧ (x1 ∨  ∨ x4) ∧ (  ∨ x4 ∨ x5) ∧ (x2 ∨ x3 ∨ )

--------------------------------------------------------------------------------
  - 이 예제에서는 x1과 x2를 참으로 하고, x3을 거짓으로 하면 전체 논리식이 참이 됨을 알 수 있다.

  - 그러나 이 문제를 해결하는 직선적인 알고리즘은 논리식에 포함된 모든 변수 xi의 값을 참 또는 거짓으로 지정하여 각 경우에 대하여 전체 논리식이 참 또는 거짓인지 검토해야 하므로 논리식을 구성하는 논리변수의 수를 n이라 할 때, O(2ⁿ)의 수행시간 복잡도를 갖는다.

■ 해밀토니언 사이클(Hamiltonian Cycle) 문제