Figure 11.1: Commonly believed relationship between P and NP
| search | 0/1 knapsack |
| shortest paths | traveling salesperson |
| spanning trees | scheduling |
| ... | ... |
| good times - leave alone | scope for improvement |
Deterministic algorithms:
Nondeterministic algorithms:
Choice of paths (non-deterministic part)
Success or failure of computation depends on choice. (Algorithm must provide the verification of proposed solution (polynomial part).)
Recall:
If x
From the way a nondeterministic computation is defined, it follows that the number 0
can be output iff there is no j such that x = A[j]
If the number of alternatives for choice is finite then we can convert the nondeterministic alg. to a deterministic alg.
for all possible values of j = choice(1:n) do It is possible to construct a nondeterministic algorithm for which many different
choice sequences lead to successful completions. NSort (Algorithm 11.2) and NPath illustrate.
Guess answer and verify ( not completely magic :-), we still need to
check/define what problem we are solving)
Given a graph G with edge costs, does there exist a path from s to t of cost < M.
Choice statement takes 0(1)
Decision : feasible solution (yes/no answer)
Optimization : feasible solution which optimizes objective function
Remember the decision algorithm for DHC:
// Does G contain a Hamiltonian Cycle?
p = choice ( all permutations of V)
let p = u1, u2, u3, ..., un
if ((u1, u2)
If |V| = n then n! choices, for non-deterministically, each particular choice O(|E|) (to check).
// Is there a clique of size at least k
S = choice (over all subsets of V of size k)
// Verify
if { (u, v)
// end Dec_Clique
However, note that optimizing criteria can be built into definition of feasibility
size of clique = number of nodes in clique
The max clique problem is an optimization problem to determine the clique of maximum size
Optimization : find size of max clique in G -- opt_clique(G)
Decision : does G contain a clique of size at least k -- dec_clique(G,k)
Relation between opt_clique and dec_clique:
Two problems L1 and L2 are said to be polynomially equivalent iff L1
True for deterministic and nondeterministic algorithms. Can we write dec_clique using opt_clique (try before looking)
T(opt_clique) = g(n)
Hence, dec_clique and opt_clique polynomially
equivalent
Decision: does there exist a path from s to t in G of cost < M
Optimization: find the length of the shortest path in G from s to t.
if T(dec_path) = f(|input|) (see page 244 for how the representation affects the time)
|input| = adjacency matrix (list) + space to store costs
G = (V,E) , | V | = n, | E | = m
c = max cost of any edge
|input| = n2 + mlog c bits
T (dec-path) = f (n2 + mlog c)
T (opt-path) = (n-1) * c * f(n2 + mlog c)
T (opt-path) not within a polynomial factor of T(dec-path).
Exercise: can you write opt-path in terms of dec-path such that T(opt-path) < p (|input|) * T (dec-path)? more
boolean variables: x1, x2, . . ., xn xi
a literal is either a variable or its negation (denote here ¯x¯i): x1, ¯x¯1, x2, ¯x¯2, . . ., xn, ¯x¯n,
Boolean formula composed of literals,
(x1 V ¯x¯2 V x4) (example: (T, F, F, ?, ?) works)
Conjunctive Normal Form CNF:
clause: literals, V with
clauses anded together
as opposed to Disjunctive Normal Form DNF
Satisfiability: given a collecton of variables x1, . . ., xn and a set of clauses
ci, 1 < i < m, is there a truth assignment (true/false) for xi's
such that c1 (Actually, the satisfiability problem is to determine whether a formula is true for some assignment. CNF-Satisfiability is the satisfiability problem for CNF formulas.)
non-deterministic alg.
Evaluate each clause
T (nEval) = O(m,n)
deterministic algorithm:
P = set of all decision problems which can be solved by deterministic algorithms in polynomial time
NP = set of all decision problems which can be solved by nondeterministic algorithms in polynomial time
P
P
Identify 'toughest' problems in NP.
NP - complete
L
There exist problems in NP not contained in NP-complete
Figure 11.2 Commonly believed P, NP, NP-Complete and NP-hard
Cook's Theorem: Satisfiability is in P iff P = NP
Cook's theorem forms the basis for identifying problems which are NP-complete. Why this is so important? So, first a reminder on reductions
L1 reduces to L2 if we can solve L1 in deterministic polynomial time using a deterministic polynomial time algorithm for L2. (Definition 11.4 of text)
(L1
Furthermore, I2 can be produced from I1 in det. poly. time
T(DET_L1) =T(DET_L2) + Poly
Ex:
dec-path
opt-clique
"reduces" is transitive
call L2 call L3 :
end end end
Note that all NP-Complete are NP-Hard, but not all NP-Hard are NP-Complete. From text: (page 506)
OK, think about this. NP-Hard is "harder" than NP-complete because NP-Complete must be NP-Hard and be in NP. That is,
there is an NP algorithm for NP-Complete, but either there is not an NP algorithm or the problem is not a decision problem for NP-hard.
Given L1 IF you could also show that L2 has an NP algorithm, then it would be NP-Complete. If I cannot, the best I can say is that it is NP-Hard
Result of some computations not uniquely determined. One of many values could result.
Algorithm Search (A[1:n], x)
If x
j := Choice (1:n);
// end search
if x = A[j] then {write (j); Success();}
write (0); Failure();
Algorithm Dsearch (A[1:n], x)
if A (j) = x then return ('success')
return ('failure')
end
//end search
nAlgorithm NPath (G, s, t, M)
Time complexity of non-deterministic algorithms:
p = < s >
end Npath
for i = 1 to n-1 do
// guess next node on path//
end // do
j = choice(1:n)
if j
// already in path, would have made a loop
if j = t then {
p = p || t ;
p = p || j
exit}
//guess complete - have end of path//
compute cost of p
if cost < M then return ('success')
else return ('failure')
Optimization vs decision problems
We will see that no optimizations can be NP-complete, only decision
Algorithm DHC( G= (V, E) )
// Guess
then return('Success')
else return('Failure')
Clique
A maximul complete subgraph of a graph G = (V, E) is a clique.
Algorithm Dec_Clique( G= (V, E), k )
// Guess - choice will give me a clique of size k (if there is one)
then return('Success')
else return('Failure')
choices (subcliques of size k) (remember (pg 10) this is equal to n!/ k!(n - k)! ) (see also page 378 of text) ; for each particular choice O(k)Clique
A clique is a maximal complete subgraph of a graph G=(V,E).
Algorithm opt_clique(G)
T(dec_clique) = f(n)
for k = n to 1 by -1
end opt_clique
if dec_clique (G,k) = true
then return (k)
end
T(opt_clique) < n * f (n)
L2 and L2 L1
Algorithm dec_clique(G, k)
maxk := opt_clique (G);
end dec_clique
if maxk > k then Success();
else Failure();
T(dec_clique) = g(n)
Shortest path from s to t in G.
Algorithm opt_path (G)
Assume : all costs are integers
c = max cost of any edge in G
L = (|V| - 1) * c
for Min = 1 to L do
if dec_path (G, Min) = true
end
return (infinity)then return (Min)
end opt_path
then T(opt_path) = (|V|-1) * f(|input|)
Satisfiability
{0,1}
(and) , V (or) .
(x2 V ¯x¯3 V ¯x¯4)
(¯x¯2 V x4 V ¯x¯5)
c2 . . . cn= true
Algorithm nEval (x [1:n], c[1:m])
|input| = O(m,n)
for i = 1 to n
end
x (i) = choice (true, false)
end
Evaluate c1 c2 . . . cm
if result is true then return (success)
else return (failure)
Algorithm dEval (x [1:n], c [1:m])
T (dEval) = O(2n mn)
for all 0/1 n - vectors x do
end dEval
Evaluate Boolean formula with chosen n-vector
end
if formula is true
then return ('success')
return ('failure')P vs NP : decision problems
NP :
just add dummy choice statements.
NP (proper subset?) P =? NP unresolved (can't prove it is, can't prove it isn't)
NP
NP-complete =
P, then P = NP)
P then P NP)
Cook's Theorem
When we see Cook's proof, we will see how he shows that if a language L is in NP, then that language L
SAT. He does this by
showing that a Universal Turing Machine reduces to the Satisfiability Problem. Very cool since the idea is that a Universal Turing
Machine can solve any problem (determinitic or not) that is computable.
Then, if SAT can ever be shown to be in P, since everything in NP reduces to SAT, then clearly P=NP.
As always, the hard part is the reduction. L2)
For every instance I1 L1, there exists an instance I2 L2 such that solution for I1 can be obtained from the solution for I2 in deterministic polynomial time.
dec-clique
L1 opt-clique opt-path dec-clique L2
proc L1 (I1, S1)
end L1
convert I1 to an instance I2 of L2
call L2 (I2, S2) //S2 is soln for I2
convert S2 to soln. S1 for I1
proc L2 (I2, S2)
. . .
end L2
L1
L2 and L2 L3 
L1 L3
proc L1 proc L2 proc L3
Definitions:
L).
NP. NP-Hard
It is easy to see that there are NP-hard problems that are not NP-complete. Only a decision problem can be NP-complete. However, an optimization problem may be NP-hard. Furthermore if L1 is a decision problem and L2 an optimization problem, it is quite possible that L1
L2. One can trivially show that the knapsack decision problem reduces to the knapsack optimization problem. For the clique problem one can easily show that the clique decision problem reduces to the clique optimization problem. In fact, one can also show that these optimization problems reduce to their corresponding decision problems. Yet, optimization problems cannot be NP-complete whereas decision problems can. There also exist NP-hard decision problems that are not NP-complete. Figure 11.2 shows the relationship among these classes.
NP-Hard. Show L1 L2 L2 NP-Hard
Also from the text:
Example 11.10 As an extreme example of an NP-hard decision problem that is not NP-Complete consider the halting problem for deterministic algorithms. The halting problem is to determine for an arbitrary deterministic algorithm A and an input I whether algorithm A with input I ever terminates (or enters an infinite loop). It is well known that this problem is undecidable. Hence there exists no algorithm (of any complexity) to solve this problem. So, it clearly cannot be in NP.
To show satisfiability the halting problem, ...
...
(I will look at this later in the course OK, time )
To show satisfiability the halting problem, simply construct an algorithm A whose input is a propositional formula X. If X has n variables, then A tries out all 2n possible truth assignments and verifies whether X is satisfiable. If so, then A stops. If it is not, then A enters an infinite loop. Hence, A halts on input X if and only if X is satisfiable. If we have a polynomial time algorithm for the halting problem, then we could solve the satisfiablity problem in polynomial time using A and X as input to the algorithm for the halting problem. Hence, the halting problem is an NP-hard problem that is not in NP.
