CSCE 411 Lecture 30

Lecture Slides

« previous | Wednesday, November 7, 2012 | next »

Categorization of Problems

We'll consider a computational problem tractable iff it can be solved in polynomial time ($O(n^{k})$ for some $k$)

Class P

tractable decision problems (with yes/no answer)

Class NP

All decision problems for which a candidate solution can be verified in polynomial time.

(We may not be able to find the solution, but we can verify the solution in polynomial time if someone is so kind to give us the solution.)

P is a subclass of NP, but ...

Many practical problems in computer science, math, operations research, engineering, etc. are poly time verifiable but have no known poly time algorithm.

Sudoku

The problem is given as an $n^{2}\times n^{2}$ array which is divided into blocks of $n\times n$ squares.

Some array entries are filled with an integer in the range $[1,n^{2}]$.

Goal is to complete the array such that each row, column, and block contains each integer from $[1,n^{2}]$.

It's difficult to solve, but easy to check.

Hamiltonian Cycle

A Hamiltonian cycle in an undirected graph is a cycle that visits every node exactly once.

Solving a problem: is there a Hamiltonian cycle in graph $G$?

Verifying a candidate solution: Is $v_{0},v_{1},\ldots ,v_{\ell }$ a Hamiltonian cycle of graph $G$?

P v. NP

Although poly-time verifiability seems like a weaker condition than poly time solvability, no one has been able to prove that it is weaker (i.e. it describes a larger class of problems).

So it's unknown whether $P=NP$

Question posed in around 1970

• Great theoretical interest
• Great practical importance:
  • If your problem is NP-complete, then don't waste time looking for an efficient algorithm. Instead look for efficient approximations, heuristics, etc.

Two cases:

1. $P\subset NP\subset {\text{All problems}}$
2. $P=NP\subset {\text{All problems}}$

NP-Complete Problems

Class of "hardest" problems in NP, symbol is NPC

If an NP complete problem can be solved in poly time, then all NP problems can be solved in poly time.

Two cases become:

1. $P\subset NP$, $NPC\subset NP$, $NP\subset {\text{All problems}}$
2. $P=NP=NPC\subset {\text{All problems}}$

Decision Problems and Formal Languages

Language: A set of strings over some alphabet

Every abstract problem has to be represented somehow for the computer to work on it (binary)

Consider "Is $x$ prime?". Numbers have to be stored in binary.

P is set of decision problems that can be computed in time $O(n^{k})$ where $n$ is the length of the input string and $k$ is a constant.

"Computed" means there is an algorithm returns YES or NO whether the string is in the language.

Verifying to solving: candidates.each do |solution|

 return :yes if solution.works?
 no

end

"Does $G$ have a Hamiltonian cycle?": $n!$ candidates

Polynomial Reduction

Relating one decision problem with another

polynomial reduction (or transformation) from language $L_{1}$ to language $L_{2}$ is a function $f$ from strings over $L_{1}$'s alphabet to strings over $L_{2}$'s alphabet such that

1. $f\in O(n^{k})$
2. $\forall x(x\in L_{1}\iff f(x)\in L_{2})$

Take a decision problem and somehow magically encode input as a sudoku problem.

$L_{2}$ is at least as hard as $L_{1}$:

• $Y\mapsto Y$ and $N\mapsto N$
• computable in poly time
• Notation $L_{1}\leq _{p}L_{2}$