P vs NP Problem

Description:

• Decision problem
• 

P:

• Stands for “polynomial time.”
• Represents the class of problems that can be solved by a deterministic Turing Machine in polynomial time
• ex:
  • Primes nb
  • Max Flow
  • Shortest Path

NP:

• Stands for “nondeterministic polynomial time.”
• Represents the class of problems where a solution can be verified in polynomial time on a non-deterministic Turing machine
• Meaning it is hard to find solution but checking a potential solution is easy
• ex: Factoring
• $P\subseteq NP$
  • Suppose that X is a problem in P.
  • By definition, there exists a poly-time algorithm A that solves X.
  • Certificate: $t$
  • Certifier $C(s,t)=A(s)$

NP-Hard:

• A problem Y (probably not in NP) with the property that for every problem X in NP, $X{\le }_{P}Y$
  • If P ≠ NP, then NP-hard problems could not be solved in polynomial time.
  • All NP-complete problems are also NP-hard
  • There are decision problems that are NP-hard but not NP-complete (halting problem)
  • SAT can be reduced to the halting problem
• Halting Problem

NP-Complete:

• A problem is NP-complete if it is both:
  • In NP: A solution can be verified in polynomial time.
  • NP-hard: Any problem in NP can be reduced to it in polynomial timete
• A problem Y in NP with the property that for every problem X in NP, $X{\le }_{P}Y$
• theorem Suppose Y is an NP-Complete problem. Then Y is solvable in poly-time iff $P=NP$
• ex:
  • Hamilton Cycle
  • Boolean Stisfiability Problem
    • Prove 3-SAT is NP Complete: Suffices to show that CIRCUIT-SAT ${\le }_P$ 3-SAT since 3-SAT is in NP
      • Let $\mathrm{K}$ be any circuit.
      • We associate a variable $x_v$ with each node $v$ of the circuit
      • If node $v$ is labeled with $\neg$, and its only entering edge is from node $u$ : we add two clauses $\left(x_v\vee x_u\right)$, and $\left(\overline{x_v}\vee \overline{x_u}\right)$.
      • If node $v$ is labeled with $\vee$, and its two entering edges are from nodes $u$ and $w$, we add the following clauses: $\left(x_v\vee \overline{x_u}\right),\left(x_v\vee \overline{x_w}\right)$, and $\left(\overline{x_v}\vee x_u\vee x_w\right)$,
      • If node $v$ is labeled with $\wedge$, and its two entering edges are from nodes $u$ and $w$ : we add the following clauses: $\left(\overline{x_v}\vee x_u\right),\left(\overline{x_v}\vee x_w\right)$, and $\left(x_v\vee \overline{x_u}\vee \overline{x_w}\right)$.
      • For a source $v$ that has been labeled with a constant value, we add a clause with the single variable $x_v$ or $\overline{x_v}$
      • For the output node o, we add the single-variable clause $x_o$
    • example of reduction: $(0\vee a)\wedge (\neg b)=1$
      • Create an instance of 3-SAT with 6 variables: $x_0,x_1,x_2,x_3,x_4,x_5$, corresponding to 6 circuit elements
        • $x_0=x_1\wedge x_2=(x_5\vee x_4)\wedge (\neg x_3)$
      • Make circuit compute correct values at each node
        • $x_2=\neg x_3\Rightarrow$ add 2 clauses: $x_2\vee x_3,x_2\vee x_3$
        • $x_1=x_4\vee x_5\Rightarrow$ add 3 clauses: $x_1\vee x_4,x_1\vee x_5,x_1\vee x_4\vee x_5$
        • $x_0=x_1\wedge x_2\Rightarrow$ add 3 clauses: $\overline{x_0}\vee x_1,\overline{x_0}\vee x_2,x_0\vee \overline{x_1}\vee \overline{x_2}$
      • Hard-coded input values and output value
        • $x_5=0\Rightarrow$ add 1 clause: $\overline{x_5}$
        • $x_0=1\Rightarrow$ add 1 clause: $x_0$
      • Final step: turn clauses of length $<3$ into clauses of length exactly 3
    • Suppose that the given circuit K is satisfiable. The satisfying assignment to the circuit inputs can be propagated to create values at all nodes in K. This set of values clearly satisfies the constructed 3-SAT instance.
    • Suppose that the constructed 3-SAT instance is satisfiable, with a satisfying. Look at the values of the variables corresponding to the circuit K’s inputs, and claim that these values constitute a satisfying assignment for the circuit K. This is because the 3-SAT clauses ensure that the values assigned to all nodes of K are the same as what the circuit computes for these nodes.
  • Independent Set
  • Subset Sum Problem
  • Knapsack Problem
  • Circuit Satisfiability Problem
• Proving NP-compleness:
  • Given an NP-complete problem, how to prove that a problem Y is NP-complete.
    • Step 1. Show that Y is in NP.
    • Step 2. Choose an NP-complete problem X.
    • Step 3. Prove that $X{\le }_{P}Y$
  • Justification. If X is an NP-complete problem, and Y is a problem in NP with the property that $X{\le }_{P}Y$ then Y is NP-complete.
  • Proof. Let W be any problem in NP. Then $W{\le }_{P}X{\le }_{P}Y$
    • By transitivity, $W{\le }_{P}Y$. Hence Y is NP-complete
  • Refined strategy:
    • Step 1: Prove that X ∈ NP.
    • Step 2. Choose a problem Y that is known to be NP-complete.
    • Step 3. Consider an arbitrary instance s(Y) of problem Y, and show how to construct, in polynomial time, an instance s(X) of problem X that satisfies the following properties:
      • (a) If s(Y) is a YES-instance of Y, then s(X) is a YES-instance of X.
      • (b) If s(X) is a YES-instance of X, then s(Y) is a YES-instance of Y