CSCE 411 Lecture 31

Lecture Slides

« previous | Friday, November 9, 2012 | next »

Culture Assignments: Turing centennial things on course website.

Polynomial Reduction

How can we be so convinced that P and NP are not the same? We don't have any evidence that they are or are not the same.

Transformation between two languages so that a YES in one language maps to a YES in the other, and the same with NOs

Anything not in the first language must map to something not in the second language.

Example: Turn a graph into a sudoku problem. If the sudoku has a solution, then the graph must have a Hamiltonian cycle. If the sudoku is unsolvable, then the graph must not have a Hamiltonian cycle.

Theorem

If $L_{1}\leq _{p}L_{2}$ and $L_{2}$ is in $P$, then $L_{1}$ is in $P$

Proof

Let $A_{2}$ be a polynomial time algorithm for $L_{2}$. Here is a polynomial time algorithm $A_{1}$ for $L_{1}$:

input: x
compute f(x)
run A[2] on input f(x)

Implications

Suppose that $L_{1}\leq _{p}L_{2}$

• If there is a polynomial time algorithm for $L_{2}$, then there is a poly time algorithm for $L_{1}$
• If there is no poly time alg for $L_{1}$ then there is no poly time alg for $L_{2}$

Hamiltonian Cycles (HC) and the Traveling Salesman Problem (TSP)

TSP: Given a set of cities, distances between all pairs of cities, and bound $B$, does there exist a tour that returns to the start and requires at most distance $B$ to be traveled?

TSP is in NP: Given a candidate solution, add up all the distances and compare total with $B$

Theorem

$HC\leq _{P}TSP$

Proof

Find a way to transform (reduce) any HC input (G) into a TSP input (cities, distances, B) such that

• the transformation takes poly time
• HC input is a YES instance (G has HC) iff TSP input constructed is a YES instance (has a tour that meets the bound)

Given undirected graph $G=(V,E)$ with $m$ nodes, construct TSP like this:

• set of $m$ cities, labeled with names of nodes in $V$
• distance betw. $u$ and $v$ is 1 if $(u,v)\in E$, 2 otherwise
• bound $B=m$

Check that input $G$ is in HC iff the input constructed is in TSP.

Suppose $G$ has HC $v_{1},\ldots ,v_{m},v_{1}$. Then TSP input $v_{1},\ldots ,v_{m},v_{1}$ is a tour and its distance is $m$

Suppose TSP input has tour of length at most $m$. Since all distances are ethier 1 or 2, and there are $m$ edges in a tour, all distances in the tour must be 1.

Transitivity of Reduction

If $L_{1}\leq _{p}L_{2}$ and $L_{2}\leq _{p}L_{3}$, then $L_{1}\leq _{p}L_{3}$.

If $f:L_{1}\to L_{2}$ and $g:L_{2}\to L_{3}$, then $f\circ g:L_{1}\to L_{3}$

NP-Completeness

$L$ is NP-Complete iff

1. $L$ is in NP and
2. for all $L'$ in NP, $L'\leq _{p}L$

In other words, $L$ is at least as hard as every language in NP.

Theorem

Suppose $L$ is NP-complete.

1. If there is a poly time algorithm for $L$, then $P=NP$
2. If there is no poly time algorithm for $L$, then there is no poly time algorithm for any NP-complete language.

Showing NP-Completeness

How to show that a problem (language) $L$ is NP-complete Show that

1. $L$ is in NP
2. every other language in NP is polynomially reducible to $L$

Better approach. Once we know some NP-complete problems, we can use reduction to show other problems are also NP-complete.

Suppose that $B$ is an NP-complete problem.

Given we know

1. $L\in NP$
2. $B\leq _{p}L$

For all $L'\in NP$, we know $L'\leq _{p}B$ and $B\leq _{p}L$. By transitivity, $L'\leq _{p}L$