## 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
- decision problems
- reductions
- 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**

- $ L \in NP $
- $ 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.

#### 34.5 NP-complete problems