CLRSch34 NPCompleteness
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
 decision problems
 reductions
 the first NPcomplete 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 polynomialtime algorithm can compute the encoding $ 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 polynomialtime 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 polynomialtime 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 Polynomialtime 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 coNP
 set of languages L such that $ \bar L \in NP $
 Since P is closed under complement, $ P \subset NP \cap coNP $
Four possibilities for relationship among complexity class
34.3 NPcompleteness 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 )
NPcompleteness
 $ L \in NP $
 $ L’ \le_p L $ for every $ L’ \in NP $. (hardest)
Theorem 34.4
 If any NPcomplete problem is polynomial time solvable, then P = NP
 If any problem in NP is not polynomialtime solvable, then all NPcomplete problems are not polynomialtime 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 NPhard
 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.