CLRS-ch34 NP-Completeness

Intro

class P

• problems are solvable in polynomial time

class NP

• problems are verifiable in polynomial time

class NPC

• problems in NP and is as hard as any problem in NP
• 3 concept showing a problem is NPC
1. decision problems
2. reductions
3. the first NP-complete problem

Decision problems vs. optimization problems

• optimization problems : find a feasible solution with the best value.
• decision problems : answer is simply “yes” or “no”
• Relationship : decision is no harder

Reductions

• $A \longrightarrow B$
• If B polynomially solvable, than A solvable
• If A polynomially unsolvable, than B unsolvable as well

34.1 Polynomial time

Abstract Problems

• a binary relation (function) on a set $I$ of instances and a set $S$ of solutions

Concrete Problems

• problems whose instance set $I$ is the set of binary strings

Polynomial time solvable

• exist an algorithm to solve a concrete problem in $O(n^k)$

Encodings

• a mapping e from the set of abstract object to the set of binary strings (abstract pro instances –> concrete pro ins)
• extend the definition of class P into abstract problems
• Abstract Pro $\longrightarrow$ Encode $\longrightarrow$ Concrete Pro $\longrightarrow$ Algorithm Solve
• depending on the encoding, the algorithm may runs in either polynomial or superpolynomial time.

• polynomially related encodings

• exist a polynomial-time algorithm can compute the en-coding $e_2 (i)$ from the encoding $e_1 (i)$, and vice versa.
• Only when two encodings $e_1$ and $e_2$ of an abstract problem are polynomially related, whether the problem is polynomial-time solvable or not can be independent of which encoding we use.

Therefore

Assume reasonable/standard encoding $< G >$

• encoding of an integer is polynomially related to its binary representation
• encoding of a finite set is polynomially related to its encoding as a list of its elements
• derive encodings of other object

so that the choice of encoding has no effect on whether the abstract problem is polynomial-time solvable.

A formal language framework

• alphabet $\Sigma$ a finite set of symbols $\{ 0,1 \}$
• language $L$ over $Σ$ is any set of strings made up of symbols from $Σ \ \{ 10, \ 11, \ 101 … \}$
• $\Sigma ^*$ the language of all strings over $Σ$

view instances for any decision problems Q as a language L over $Σ = \{ 0 ,1 \}$

Accepted

• The language L accepted by an algorithm A $L = \{ x \in \{0,1\}^* : A(x) = 1 \}$
• Reject : A(x) = 0
• may runs forever if doesn’t accept

Decided

• The language L decided by an algorithm A
• if every binary string in L is accepted by A (output 1) and every binary string not in L is rejected ( output 0)
• $x \in L$ –> A(x) = 1, $x\notin L$ –> A(x) = 0

Complexity class P

$P = \{ L \subseteq \{ 0,1 \}^{*}$ : exists an algorithm A that decides L in polynomial time $\}$

34.2 Polynomial-time verification

algorithms verify membership from a certificate in languages

Verified

• The language L verified by an algorithm A $L = \{ x \in \{ 0, 1 \}^ :$ there exist $y \in \{ 0,1 \}^$ such that A( x,y ) = 1 $\}$

Complexity class NP

$NP = \{ L \subseteq \{ 0, 1 \}^ : L = \{ x \in \{ 0,1\}^$ : there exists a certificate y with |y| = $O(|x|^c)$ such that A(x,y) = 1 $\} \}$

$P \subseteq NP$

Complexity class co-NP

• set of languages L such that $\bar L \in NP$
• Since P is closed under complement, $P \subset NP \cap co-NP$

Four possibilities for relationship among complexity class

34.3 NP-completeness and reducibility

Reducibility

• if $Q \longrightarrow \ reduce \ \longrightarrow Q’$ , $Q$ is “no harder to solve” than $Q’$
• $Q \le_p Q’$ ( no more than a polynomial factor harder )

NP-completeness

1. $L \in NP$
2. $L’ \le_p L$ for every $L’ \in NP$. (hardest)

Theorem 34.4

• If any NP-complete problem is polynomial time solvable, then P = NP
• If any problem in NP is not polynomial-time solvable, then all NP-complete problems are not polynomial-time solvable.

Circuit satisfiability

Given a boolean combinational circuit composed of AND, OR, and NOT gates, is it satisfiable?

34.5 belongs to NP

34.6 NP-hard

• basic idea : represent the computation of A(algorithm verify L) as a sequence of configurations.
• Each configuration is mapped to the next configuration by a boolean combinational circuit M. The output is a distinguished bit in the working storage.
• The reduction algorithm F constructs a single combinational circuit that computes all configurations produced by a given initial configuration.