Re: 6P=NP: Proof: Nondeterministic Algorithm
- From: Martin Musatov <marty.musatov@xxxxxxxxx>
- Date: Wed, 13 May 2009 16:05:58 -0700 (PDT)
On May 13, 3:29 pm, Martin Musatov <marty.musa...@xxxxxxxxx> wrote:
Nondeterministic algorithm
Nondeterministic algorithms have two phases:
1. Nondeterministic guessing (think of as some random process)
phase, each time the algorithm is run the resulting guess may differ.
2. Deterministic verification phase, checks that the guess is a
solution, returning true or false, or looping infinitely.
Example: Nondeterministic graph coloring
Use 4 colors to color 5 vertices with all adjacent vertices a
different color.
Guesses (vertex order 1-5):
* RRRRR false All vertices Red
* RYBRG false Adjacent vertices 1 and 4 Red
* RBYGO false Too many colors (5) used
* RGRBY true Valid 4-coloring
The First NP-Complete Problem
Circuit-Satisfiability - given a Boolean circuit constructed from
AND, OR and NOT gates, determine whether there is any set of Boolean
inputs to the circuit that causes an output of 1.
Solution - See truth table at bottom right.
Question - To develop some intuition on determinism and NP-
completeness, do the following on Figure (b) below:
1. How would you solve for one output solution for x1, x2 and
x3?
2. Try to guess and verify one solution for x1, x2 and x3. Your
guess is nondeterministic but the verification is deterministic.
3. What is the worst-case complexity in determining the input
to produce an output of 1?
4. What is the complexity in verifying a given input produces
an output of 1? Consider the number of operations (gates) that must be
evaluated.
Figure 34.8 (a) and (b) from Cormen
Circuit (b) = ((Øx3Ùx1Ùx2)ÚØØx3)Ù((x1Úx2)ÙØØx3)Ù(Øx3Ùx1Ùx2)
x1 x2 x3 Output
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 1
1 1 1 ?
Verifying
Given assignments to x1, x2, and x3, verification can easily
be done in O(nk) or polynomial time.
if ((Øx3Ùx1Ùx2)ÚØØx3)Ù((x1Úx2)ÙØØx3)Ù(Øx3Ùx1Ùx2) then
print 1 else print 0
NP-completeness and the class P and NP
class P - Polynomial or O(nk) for k a constant
Consists of those problems that are solvable in polynomial
time by a deterministic algorithm.
Its worst case efficiency is O(p(n)) where p(n) is a
polynomial.
Note that for O notation, problems solvable in logarithmic or
linear time are polynomial.
class NP - Nondeterministic Polynomial
Consists of those problems that are verifiable in polynomial
time.
If given a solution, could verify the solution is correct in
time polynomial based on the size of the input to the problem.
Example: We just demonstrated graph coloring can be verified
correct in polynomial time.
Example: Hamiltonian Cycle Problem - Find a cycle in a graph
visiting each vertex exactly once.
Example: 2®3®4®5®1
Given: an undirected graph G = (V, E)
A certificate would be a sequence of |V| vertices <v1,
v2, ..., v|V|>
To verify:
* check that each edge in the sequence (vi, vi+1)
Î E(G), " i: 1 ≤ i ≤ |V| - 1
* and the edge (v|V|, v1) Î E(G).
Verification can be done in polynomial time, W(|V|)
P Í NP
class NPC - NP Complete
Consists of problems in NP and are as hard as any problem in
NP
If any problem in NPC can be solved in polynomial time, then
all problems in NPC can be solved in polynomial time.
Abstract Problems
abstract problem Q - a binary relation that associates each instance
with a solution
Let set I be a set of problem instances
Let set S be a set of problem solutions
Then Q is a binary relation on I and S, Q Í I x S
I x S can have empty or non-unique solutions
Example
A Path problem instance is the input: a triple (G, u, v),
where G is a directed graph and u and v are vertices in the graph.
At right: G =( V, E ), u=s, v=x.
Path's I - is the set of all problem instances of the Path
type. I = {i1, i2, ... }, where each ij is of the form (G, u, v).
(G,s,x) represents one instance of I.
Path's S - is the set of all Path solutions. S = {s1,
s2, ... }, where each sj is of the form <v1, v2, ..., sn >, a
sequence of vertices in the graph, or <Æ> if no path exists.
For the graph, one instance of S is the path
<s,y,z,x>.
For the graph, one instance not of S is the path <x,
s>.
The Path Abstract Problem (PAP):
* Is a relation PAP Í I x S such that members of the
relation are tuples of the form (ij, sk) and appear in the relation
only when solution sk is a solution to problem instance ij.
o Example: ij=(G, s, x), sk=<s,y,z,x> so (ij,
sk) Î PAP, that is an (instance, solution) tuple.
* (ij, sk) does not appear in PAP if sk is not a
solution to problem instance ij
* ij may appear in PAP more than once since there may
be more than one solution to problem instance ij
abstract decision problem D - a binary relation that associates each
instance with a yes/no solution
Let I be a set of decision problem instances
Let S be the set {0, 1}
Then D is a binary relation on I and S, D Í I X S and every tuple
in D has the form (ij, sk) with sk = either 0 or 1
Example
The Path abstract decision problem is a four-tuple (G, u,
v, k), where G is a graph and u and v are vertices in the graph, and k
is the upper limit on the number of edges in the path from u to v.
Path's I - is the set of all problem instances of the Path
type. I = {i1, i2, ... }, where each ij is of the form (G, u, v, k)
Path's S - is the set of all Path solutions. S = {0, 1}
The Path Abstract Decision Problem (PADP):
* Is a relation PADP Í I X S such that members of the
relation are tuples of the form (ij, sk) and "j ij Î I then (ij, 0) Î
PADP or (ij, 1) Î PADP, where sk = 0 if there does not exist a path
from u to v of at most k edges and sk = 1 if a path does exists with
at most k edges.
Examples:
o ij=(G, s, z, 20), sk=1
o ij=(G, s, z, 1), sk=0
Summary
To develop a method for showing a problem is NP-complete, we
need a general representation of problems (abstract) and that have a
yes/no answer (decision).
Algorithm's that verify membership in a language
x - a problem instance (input string)
y - a certificate (solution string)
A - an algorithm, verifies x if there exists a certificate y such
that A(x, y)=1
Language verified by A is:
L = {x Î {0, 1}* : $ certificate y Î {0, 1}* such that A
(x, y) = 1}
Algorithm A verifies language L if for any string x Î L, there
is a certificate y that A can use to prove that x Î L.
For any string, x Ï L, there is no certificate proving that x
Î L.
Example: Hamiltonian graph cycle (HAM-CYCLE) is a simple cycle
that contains each vertex.
The certificate is the list of vertices in the Hamiltonian
graph cycle, enough information for verification
(e.g. vertices <1, 2, 3, 4, 5>)
If not Hamiltonian, there is no list that can fool the
verification algorithm.
Algorithm A would not be fooled by <2, 1, 3, 4, 5>
L is just those input strings of vertices which are a
Hamiltonian cycle.
{<1, 2, 3, 4, 5>, <2, 3, 4, 5, 1>, ..., <5, 4, 3, 2,
1>, ...}
Example:
For one instance of HAM-CYCLEL where:
V= {1,2,3,4,5}
E = {(1,2),(2,1),(1,5),(5,1),...}
G = (V, E)
AHAM-CYCLE( G, <1, 2, 3, 4, 5>) = 1
AHAM-CYCLE( G, <1, 2>) does not equal 1
Complexity class NP - Nondeterministic Polynomial time
A class of languages that can be verified by a polynomial-time
algorithm.
L Î NP iff $ a 2-input polynomial-time algorithm A and
constant c such that:
L = {x Î {0, 1}* : $ a certificate y with |y| = O (|x|c) such
that A(x, y) = 1}
x is the instance (input) and y is the solution to be verified
Algorithm A verifies L in polynomial time
Example: Proving PATHL Î NP
PATH problem:
xi = (G, u, v, k), where
* G is the graph,
* u is the source vertex,
* v is the target vertex,
* k is an integer specifying the maximum allowable
length of a path from u to v.
Given PATH problem instance:
x1 = (G, r, y, 5),
certificate p = < r, s, w, x, y >
use APATH (x1, p) to verify that path p's length is ≤ k
APATH (x, p) verifies p is a path in x's G of length k or less
in polynomial time by:
APATH(x, p) verifies PATHL as follows:
1. Verify x is a proper encoding of <G,u,v,k>
2. Verify each v Î p is unique, i.e. p is a set.
3. Verifies first vertex in list is: u Î x.
4. Verifies last vertex in list is: v Î x.
5. Verify length[p] ≤ k
6. for i ¬ 1 to length[p]-1 do verify (vi, vi+1) Î E[G]
7. If steps 1-6 verify, APATH (x, p) = 1
Therefore PATHL Î NP, since APATH(x, p) can produce either a 0
or a 1 in polynomial time.
But we already knew that PATH Î P, and P Î NP, i.e., anything
that can be computed in polynomial time can be verified in polynomial
time.
Reducibility - tool for proving languages belong to class P
Problem Q can be reduced to problem Q' if any instance of Q can be
easily rephrased (i.e. polynomial time) as an instance of Q'. The
solution to Q' provides a solution to Q.
L1 ≤p L2
Language L1 is polynomial time reducible to language L2 if
there exists a polynomial time function:
f : {0, 1}* ® {0, 1}* such that for all x Î {0, 1}*
x Î {0, 1}* iff f(x) Î L2
f is the reduction function, converting an instance of A1 to an
instance of A2.
F is the reduction algorithm, the polynomial time algorithm that
computes f.
For decision problem represented by L1
for any x Î L1, f(x) Î L2
F computes reduction function f.
A2 decides L2 in polynomial time.
A1 algorithm decides x Î L1 using F to transform x into f(x), then
using A2 to decide if f(x) Î L2.
If f(x) Î L2 then x Î L1.
NP-completeness
Language L Í {0, 1}* is NP-complete if:
1. L Î NP
2. L' ≤p L for every L' Î NP (meaning L' is polynomial
time reducible to L)
NP-hard - Language L that satisfies property 2 only (satisfying
property 1 means L is polynomial time verifiable, NP-hard means it is
not polynomial time verifiable).
Now to prove that NP-complete class has property that if any NP-
complete problem can be solved in polynomial time, every NP problem
can be solved in polynomial time.
Theorem 34.4
Equivalent statements:
1. If any NP-complete problem is polynomial time solvable,
then P=NP (all NP problems can be solved in polynomial time).
2. If any NP problem is not polynomial time solvable, then
no NP-complete problem is polynomial time solvable .
Proof
Let L Î P and also that L Î NPC (the class of NP-complete
languages).
For any L' Î NP, by property 2 of NP definition, L' ≤p L.
By Lemma 34.3, have L' Î P, proving the first statement.
The second statement is the contrapositive of the first
(i.e. the contrapositive of p ® q is ~q ® ~p).
A First NP-Complete problem
NP-completeness of circuit-satisfiability relies on direct proof
that L ≤p CIRCUIT-SAT for every language L Î NP.
CIRCUIT-SAT provides the known NP-complete problem to prove a
different problem NP-complete.
A language L Í {0, 1}* is NPC if:
1.
L Î NP and
2.
L' ≤p L, " L' Î NP
Seems must show all L' Î NP have to be reduced to L to show L Î
NPC.
Not so.
Transitivity, by reducing a known NP-complete language L' to L,
implicitly reduces every language in NP to L.
NP-hard - A language L that satisfies L' ≤p L, " L' Î NP (means every
language in NP can be reduced in polynomial time to L).
Lemma 34.8
L is a language such that L' ≤p L for some L' Î NPC
*
L is NP-hard.
*
If L Î NP then L Î NPC.
Proof
L'' ≤p L', " L'' Î NP property 2 in NPC
definition L' Î NPC
L is NP-hard By transitivity,
L'' ≤p L' ≤p L, so L' ≤p L, " L' Î NP.
Satisfies
property 2 of NPC.
L Î NPC If L Î NP then
satisfies property 1 of NPC definition.
Means that by reducing a known NP-complete language L' to L, we
implicitly can reduce every language in NP to L.
The General Method for proving L Î NPC
1.
Prove L Î NP by showing that a solution can be verified in
polynomial time.
2.
Select a known NPC language L' (e.g. CIRCUIT-SAT)
3.
Describe an algorithm that computes a function f that maps every
instance of x Î {0, 1}* of L' to an instance f(x) Î L
4.
Prove that the function f satisfies x Î L' iff f(x) Î L, " x Î
{0, 1}*
5.
Prove that F runs in polynomial time (F is the algorithm that
computes the function f)
Example - Prove Formula satisfiability is NPC
SAT = { <f>: f is an instance of a Boolean formula}
f is composed of:
*
n Boolean variables: x1, x2, ..., xn
*
m Boolean connectives: ^, v, ¬, ®, «
*
( ) parenthesis
Example Formula: f = ((x1 ® x2) v ¬((¬x1 « x3) v x4)) ^ ¬x2
n = 4, m = 8
*
f Î SAT if f has a satisfying assignment to xi
*
For the formula above try: x1 = 0, x2 = 0, x3 = 1, x4 =
1
*
There are 2n possible assignments to f
*
Checking all requires at least W(2n) time
Overall Steps for Showing SAT Î NPC
1.
Show SAT Î NP
ASAT(f,y) = 1
ASAT runs in polynomial time by just replacing each xi
with its corresponding value from y and evaluating expression.
Simulate f to verify certificate.
2.
Show CIRCUIT-SAT ≤p SAT
1.
Select a known NPC language L' (i.e. choose CIRCUIT-
SAT)
2.
Describe an algorithm F that computes a function f,
mapping every instance of x Î {0, 1}* of CIRCUIT-SAT to an instance f
(x) Î SAT
See below.
3.
Prove that the function f satisfies: x Î CIRCUIT-SAT
iff f(x) Î SAT, " x Î {0, 1}*
4.
Prove that F computes f in polynomial time
CIRCUIT-SAT ≤p SAT has been shown.
SAT Î NP and CIRCUIT-SAT ≤p SAT
Hence SAT Î NPC
By Lemma 34.8, if L is a language such that L' ≤p L for some
L' Î NPC, then L is NP-hard. Also, if L Î NP then L Î NPC.
That is: if SAT is a language such that CIRCUIT-SAT ≤p SAT for
CIRCUIT-SAT Î NPC, then SAT is NP-hard. Also, if SATÎ NP then SAT Î
NPC.
What is the function f ?
* Convert the circuit to a f
Example: f = ((x1 ® x2) v ¬((¬x1 « x3) v x4)) ^ ¬x2
* Label each wire in the circuit x1, x2, x3, ..., xn, these become
f's Boolean variables.
* Write a formula for each gate expressed in terms of all the
wires incident on that gate.
For example:
(x4 « ¬x3) i.e., x4 is true iff ¬x3 is true
*
F reduces CIRCUIT-SAT instance to SAT instance by converting
Boolean expressions to wire connections and gates.
f = x10 ^ (x4 « ¬x3)
^ (x5 « (x1 v x2))
^ (x6 « ¬x4)
^ (x7 « (x1 ^ x2 ^ x4))
^ (x8 « (x5 v x6))
^ (x9 « (x6 v x7))
^ (x10 « (x7 ^ x8 ^ x9)
*
For this circuit to be satisfiable, there has to be a satisfying
assignment to x1 .. x10
*
Satisfied by: x1 = 1, x2 = 1, x3 = 0, x4 = 1, x5 = 1, x6 = 0, x7
= 1, x8 = 1, x9 = 1, x10 = 1
What This Reduction Shows - CIRCUIT-SAT ≤p SAT
Already shown SAT Î NP
Reduction shows CIRCUIT-SAT ≤p SAT
Hence SAT Î NPC
So we can construct a machine as follows:
* A1 is CIRCUIT-SAT Î NPC
* A2 is SAT
* F is the polynomial-time reduction algorithm that computes
the function f
* x is a problem instance of CIRCUIT-SAT
* f(x) is a problem instance of SAT
*
If a polynomial-time algorithm existed for SAT (i.e., A2 in
the diagram), then we could construct a machine similar to Figure 34.5
that could decide A1 in polynomial time.
*
But we know that no known polynomial-time algorithm has ever
been discovered for CIRCUIT-SAT (i.e., A1 in the diagram)
*
Therefore, by contradiction, it is not likely that a
polynomial-time algorithm exists for SAT
*
A proof that a problem is NP-complete is excellent evidence
it is intractable.
6P=NP: Nondeterministic Algorithm
Martin Musatov
.
- References:
- 6P=NP: Proof: Nondeterministic Algorithm
- From: Martin Musatov
- 6P=NP: Proof: Nondeterministic Algorithm
- Prev by Date: Re: RIEMAN HYPOTHESIS
- Next by Date: Re: Mean and Stdev
- Previous by thread: 6P=NP: Proof: Nondeterministic Algorithm
- Next by thread: 6P=NP: Proof: Harvey Friedman Revised
- Index(es):
Relevant Pages
|
