NP Completeness Definition

Content

• P & NP

  source: wiki

• Definition

  • P: Polynomial-time solvable, correspond to Deterministic Turing Machine
  • NP: Polynomial-time verifiable, correspond to Non-Deterministic Turing Machine.
  • NPC: Hardest problem in NP, we say a problem $X\in NPC⟺X\in NP,\forall Y\in NP,Y{\le }_{p}X$, we can verify a NPC problem is in NP by using a certificate(solution) whose size are polynomial to the problem instance can be verified in polynomial time.

• Polynomial Time Reduction $X{\le }_{p}Y$

  • 
  • For any instance of $x$ in $X$, there is a polynomial time function that computes $f(x)=y$, and $x$ is true $iff$ $f(x)=y$ is true.
  • $Y$ is equal or harder than $X$, we can view $Y$ as a black box.

• Relation

  • If $X\in P\Rightarrow X\in NP$
  • if $X{\le }_{p}Y$
    • if $Y$ can be solved in polynomial time, then $X$ can be solved in polynomial time
    • if $X$ cannot be solved in polynomial time, then $Y$ cannot be solved in polynomial time
    • if $X{\le }_{p}Y$, and $Y{\le }_{p}X$ then $X{\equiv }_{p}Y$
  • if $X{\le }_{p}Y,Y{\le }_{p}Z\Rightarrow X{\le }_{p}Z$

Reference

• 台大電機演算法課程
• 輕鬆談演算法的複雜度分界：什麼是P, NP, NP-Complete, NP-Hard問題
• How to prove that a problem is NP complete?
• Proving that a problem is in NP