wk3 - complexity class NP & Karp reductions

(x, y) ∈ R

y is a valid solution for x

x = input

y = candidate solution

input solution relation: R ⊆ {0, 1}∗ × {0, 1}∗

an algorithm V verifies R if on input (x, y):

V (x , y ) = 1 ⇐⇒ (x , y ) ∈ R

LR = {x : ∃y (x , y ) ∈ R}

an algorithm A decides LR if on input x:

A(x ) = 1 ⇐⇒ (∃y )(x , y ) ∈ R

efficient verification only make sense if

valid solutions have reasonable size

what would make this relation polynomially bounded

R ⊆ {0, 1} × {0, 1}

if there exists a polynomial p such that for all (x, y) ∈ R:

|y| ≤ p(|x|)

(answers (solutions) are not as long as the input)

a language L is in NP if

there exists a polynomially bounded relation R and a polynomial time verifier V such that:

x ∈ L ⇐⇒ (∃y ) (x , y ) ∈ R

x ∈ L ⇐⇒ (∃y ) (x , y ) ∈ R

what is y

what is V

y is a certificate

V verifies (x, y) in polynomial time

what does NP stand for

Nondeterministic Polynomial Time

a non deterministic algorithm:

- may branch into multiple possible executions

- accepts an input if some execution path accepts

(just like how NFA can branch into multiple

NP definition

the class of languages decidable by nondeterministic programs in polynomial time

proof of P ⊆ NP

1. assume L ∈ P and M be an efficient algorithm that decides whether a given input x ∈ L

2. define R = L x {0}

(this means zero is a certificate for every input)

3. it is easy to see R is polynomially bounded

4. the verifier V(x, y): check and accept iff M(x) accepts and y = 0

(in a way, M itself acts as a verifier)

proof of NP ⊆ EXP

(EXP = exponential time complexity class)

1. let L ∈ NP; and V the verifier;

suppose certificates length for input of size n is l(n)

2. construct a solver M(x) to enumerate all possible certificates y ∈ {0, 1} ^ l(n)

and run V(x, y) on each one, if it accepts then the solver accepts

3. M accepts x iff x ∈ L

NP ⊆ EXP brute force idea

- enumerate all possible certificates y of length ≤ p(|x |)

- verify each (x, y) in polynomial time

NP is closed under union theorem

if L1, L2 ∈ NP, then L1 ∪ L2 ∈ NP

formal proof for

if L1, L2 ∈ NP, then L1 ∪ L2 ∈ NP

1. let R1, R2 be polynomially bounded relations

2. let V1, V2 be their polynomial-time verifiers

3. we need a verifier V for L1 ∪ L2 where

on input (x , b ◦ y):

- if b = 0, return V1(x, y)

- otherwise, return V2(x,y)

4. notice that if x ∈/∈ L1 ∪ L2, verifier V never accepts any certificate. otherwise if x ∈ L1, then there must be y1 such that V1(x, y1) accepts; in this case, verifier V accepts the certificate 0 ◦ y1. the case when x ∈ L2 is similar

NP is closed under intersection theorem

if L1, L2 ∈ NP, then L1 ∩ L2 ∈ NP

core idea for a certificate for L1 ∩ L2 ∈ NP

consists of two certificates;

1. a certificate for L1

2. a certificate for L2

both certificates are polynomially bounded

both certificates run in polynomial time

how would you show that NP is closed under complement, what is the issue with it?

to show x is not in L, we would need a certificate of non-existence

in general, such certificates may not exist

difference between class P and class NP

- P can be decided in polynomial time whereas NP can be verified in polynomial time

- P is equivalent to efficient decision

- NP certificates are polynomially bounded

- P is closed under complement, whereas NP closure under complement is unknown

P is efficient computation, NP efficient verification

a language A is Karp-reducible to B if there exists a polynomial-time function f such that:

x ∈ A ⇐⇒ f (x ) ∈ B

use A ≤Karp B to denote this

what do karp reductions show

all constraints of one problem can be expressed inside another problem

solving B implies solving A, preserves YES/NO answers

theoretical power of karp reductions

if A ≤Karp B, then A is no harder than B

- if B ∈ P, then A ∈ P

- if A is "hard" then B is "hard"

reductions define a partial order of computational difficulty

practical power of karp reductions

a reduction is an adapter.

translate instances of A into instances of Bm then call a solver for B

a library for B implies a solver for A

what is the goal of the reduction:

3COL ≤ karp SAT

given a graph G, we construct a boolean formula ϕ such that:

G ∈ 3COL ⇐⇒ ϕ ∈ SAT

(so G is 3 colourable iff ϕ is satisfiable)

given: G ∈ 3COL ⇐⇒ ϕ ∈ SAT

how are the variables of formula ϕ defined

for each vertex v ∈ V(G) and each colour j ∈ {1, 2, 3}, introduce a boolean variable:

x(v, j)

x(v, j) = true iff vertex v is assigned colour j

each vertex has three associates variables

total num of variables is 3|V(G)|

clause to enforce each vertex v ∈ V(G) gets a colour

given: G ∈ 3COL ⇐⇒ ϕ ∈ SAT

Cv = (x(v, 1) ∨ x (v , 2) ∨ x (v , 3))

Cv ensures that vertex v is assigned some colour |D

combine all vertices: (in image)

clause to enforce adjacent vertices get different colours j ∈ {1, 2, 3}

given: G ∈ 3COL ⇐⇒ ϕ ∈ SAT

for each edge {u, v} ∈ E(G) and colour j ∈ {1, 2, 3} define:

Q{u,v },j = (¬x (u, j) ∨ ¬x (v , j))

Q{u,v },j forbids u and v from both having color j

combine all conflicts: (in image)

final formula of ϕ

given: G ∈ 3COL ⇐⇒ ϕ ∈ SAT

ϕ = C ∧ Q

ϕ is in conjunctive normal form (CNF) with at most three literals per clause (3SAT)

the size of ϕ is O(|V(G)| + |E(G)|)

correctness proof of

a proper 3-colouring -> satisfying assignment

- let σ : V → {1, 2, 3} be a colouring

- define x(v, j) = true iff σ(v) = j

- this satisfies each clause Cv since each vertex gets a colour

- it also satisfies each clause Qe since each edge sees different colours

correctness proof of

a satisfying assignment -> proper 3-colouring

- for each clause Cv define σ(v ) = j if x (v , j) is true

- since each Qu,v is true, we have that σ(v) /= σ(u)

- therefore the colouring is proper

independent set (IS) in a graph

is a set of vertices no two of which are adjacent

what is α(G)

the size of the largest independent set in G

INDSET =

{(G, k) : G has independent set of size k}