Transcript Discrete Math

‫חישוביות וסיבוכיות‬
Computability and Complexity
Lecture 7
Outline
Last week:
• Time complexity
• The class P
Today:
• Non-deterministic TM
• The class NP
Last Week: Time Complexity
Definition: Let M be a TM that halts on all inputs. The
time complexity of M is a function f:N  N, where
f(n) is the maximum number of steps that M
performs on any input of length n.
Definition: Let t: NR+. The complexity class
TIME(t(n)), is the collection of all languages that
are decidable by an O(t(n)) time Turing machine.
Complexity vs. Computability
Computability: Church-Turing thesis
“all reasonable models of computation are equivalent”
Complexity: Choice of model may affect running time.
Which model should we use to classify the time complexity of
problems?
Idea: choose a classification system that is not sensitive to
relatively small differences in complexity.
Single and Multi-tape TM’s
Theorem: Let t(n) be a function, where t(n)  n. Then
every t(n)-time multiple TM has an equivalent
O(t2(n))-time single-tape TMs.
All reasonable (deterministic) computational models
are polynomially equivalent .
The Class P
Definition: P is the class of languages that are
decidable in polynomial time on a deterministic
single-tape TM. In other words,
P  TIME(n )
k
k
Nondeterministic TM
At any point in a computation the machine may
proceed according to several possibilities.
: Q x   P(Q x  x {L,R})
Definition: A NTM accepts an input if there is a branch
of computation that leads to the accept state.
The Computation Tree:
Each node: represents a configuration.
Each edge: a deterministic transition between
two configurations.
Each branch: a deterministic computation.
The root: the initial configuration.
The Computation Tree
On input w=010:
q0010
(q0,0)=({q1,1,R}, {q1,0,R})
(q1,1)=({q1,1,R}, {q1,0,R},{q1,1,L})
(q1,0)=({q2,1,L}, {q1,1,R})
1q110
11q10
10q10
0q110
q1110
Simulating an NTM with a DTM
Theorem: Every non-deterministic TM has an
equivalent deterministic TM.
Note: No reference to running time.
Proof:
 Every deterministic TM is a special case of
non deterministic TM.
 Simulating a NTM N with a DTM D:
Simulating an NTM with a DTM
• Construct a tree with all possible branches of the
computation.
• Search on the tree for accept state.
• Using depth first search (DFS)?
• May not halt!
• Every node has a finite number of branches,
but every branch can be infinitely long.
• Use breadth first search (BFS).
Use 3 tapes:
• Input tape: contains the input.
• Simulation tape: maintains a copy of N’s tape
on some non-deterministic branch.
• Address tape: keeps track of D’s location in N’s
computation tree (‘performs’ the BFS).
The Address Tape:
Encodes in a lexicographic order
the branches of the
computation tree.
1
1
2
2
1
3
11
2 1 1
_
_
_
1
2
2
Simulating an NTM with a DTM
1. Initially tape 1 contains w. Other tapes are empty.
2. Copy tape 1 to tape 2.
3. Use tape 2 to simulate N on one branch of its non
deterministic computation determined by tape 3.
4. Replace the string with the lexicographically next
string. Go back to 2.
Simulating an NTM with a DTM
•
In stage 3:
1.
2.
•
Before each step - consult the next symbol on tape 3.
When should go directly to 4:
a) If no more symbols remain on tape 3.
b) If nondeterministic choice is ‘invalid’
c) In case of a reject configuration.
Accept: if an accept configuration occurs.
Time Complexity of NTM
Definition: Let N be a nondeterministic decider TM. The
running time of N is the function f:N  N, where f(n) is
the max. number of steps that N performs on any
branch of its computation on any input of length n.
Theorem: Let t(n) be a function, where t(n)  n. Then
every t(n) time nondeterministic single-tape TM has an
equivalent 2O(t(n)) time deterministic single-tape TM.
Proof by Picture
reject
t(n)
b – max degree
accept
reject
O(bt(n))
Deterministic vs Non-deterministic
Time Complexity
• Last week: at most polynomial difference
between single-tape TM and multiple-tape TM.
• Today: at most exponential difference between
deterministic single-tape TM and
nondeterministic single-tape TM.
• Can we simulate NTM on DTM with only
polynomial slowdown?
The PATH Problem
Given two nodes, s and t, in a graph G, is there
a directed path from s to t?
PATH={<G,s,t> | G is a directed graph that has a
directed path from s to t}
e
d
s
c
Theorem: PATH P
t
b
a
Hamiltonian Path
A path in a directed graph G that goes through
each node of G exactly once.
HAMPATH={<G,s,t>|G is a directed graph with a
Hamiltonian path from s to t}
e
t
b
a
d
s
c
Brute-Force Search for HAMPATH
Given G with m nodes, and two nodes s, t:
1.
2.
Go over all permutations of the nodes in G.
For each permutation verify whether it is a Hamiltonian
path that starts with s and ends with t.
Number of possible paths m! = θ(mm)
=> Exponential complexity
Polynomial Verifiability
Finding a Hamiltonian path seems to be hard.
However, given a path, it is possible to verify that it is
Hamiltonian in polynomial time.
e
t
b
a
d
s
c
Another Example: Compositeness
A natural number is composite if it is a product
of two integers greater than 1.
COMPOSITES = {x | x=pq, for integers p,q>1}
COMPOSITES can be verified in poly-time: any
divisor of x can serve as a certificate .
Are all problems Verifiable in
Polynomial Time?
• HAMPATH – complement of HAMPATH: determine
whether a graph does not have a Hamiltonian path.
• But how can you verify nonexistence of something?
• Seems like we must go over all paths…
• It is unknown whether HAMPATH can be verified in
polynomial time.
Verifier for a Language
Definition: A verifier for a language A is an
algorithm V, where
A = {w |  string c s.t. V accepts <w,c> }
• V’s running time is measured in terms of |w|
• A is polynomially verifiable if it has a poly-time V
• c is the certificate or proof of membership in A
• V can verify that w is in A, given a certificate, c
The Class NP
Definition: NP is the class of languages that have a
polynomial time verifier.
NP is an important class:
1.
2.
3.
Contains problems of practical interest, such as HAMPATH
and COMPOSITES (we’ll see many more).
Captures the notion of efficiently verifiable ‘proof’ (we may
try and use it to model abstract things such as ‘creativity’).
Related to THE central open question in computer science
(is P equal to NP?).
NP: Non-deterministic Poly-time
Example: Nondeterministic TM that decides
HAMPATH
N1 = “On input <G,s,t>
1.
2.
3.
4.
Write a list of m numbers, p1,…pm, where m is the
number of nodes in G. (Nondeterministic)
Check for repetitions in the list – if exists reject.
Check that s=p1 and t=pm if not- reject.
For 1i<m, check that all (pi,pi+1) are edges in G. If not
reject, otherwise, accept.”
Note: N1 runs in polynomial time.
NP – Alternative Definition
Theorem: A language is in NP iff it can be decided
by some non-deterministic polynomial time TM.
Corollary: Any language in NP can be decided in
exponential time (why?).
Proof idea (of theorem):
 NTM simulates verifier by guessing the certificate.
 Verifier simulates NTM by using the accepting branch of
the NTM.
Proof: First Direction
Let A NP and let V be a polynomial time verifier for A.
The following NTM N decides A in polynomial time.
N = “On input w of length n.
1.
2.
3.
Non-deterministically select string c of length ≤ nk.
Run V on input <w,c>.
If V accepts, accept; Otherwise, reject.”
Proof: Second Direction
Assume that A is decided by a polynomial time NTM
N. The following V is a polynomial time verifier.
V = “On input <w,c>.
1.
2.
Simulate N on input w (c is the choices made along the
nondeterministic computation of N).
If this branch of N’s computation accepts, accept;
Otherwise, reject.
Non-deterministic Time Complexity
Definition: Let t: NR+. The time complexity class
NTIME(t(n)), is the collection of all languages that
are decidable by an O(t(n)) time non-deterministic
Turing machine.
NTIME(t(n)) = {L | L is a language decided by a
O(t(n)) time non-deterministic TM}
NP 
k
NTIME(n )
k
Example of a Problem in NP: CLIQUE
A clique in an undirected graph is a subgraph for
which every two nodes are connected.
2-clique
4-clique
CLIQUE={<G,k>|G is undirected graph
with a k-clique}
CLIQUE is in NP
Theorem: CLIQUE ∈ NP.
Proof 1: We construct a polynomial-time verifier V
for CLIQUE.
V = “On input <<G,k>,c>
1.
2.
3.
Test whether c is a set of k nodes in G.
Test whether G contains all edges connecting nodes in c.
If both pass, accept; Otherwise, reject. “
CLIQUE is in NP: Alternative Proof
Proof 2: We construct a polynomial NTM N that
decides CLIQUE.
N = “On input <G,k>
1. Non-deterministically select subset c of k nodes in G.
2. Test if G contains all edges connecting nodes in c.
3. If yes, accept; Otherwise, reject.”
Example II: SUBSET-SUM
• X = {x1,…,xk} – a collection of numbers (with repetitions)
• t – a target number
• is there a subset of the collection that adds up to t?
SUBSET-SUM  { X , t | X   x1 ,
y ,
1
, y j    x1 ,
, xk  and for some
, xk  , we have  yi  t}
Example: <{4,11,16,21,27},25> ∈ SUBSET-SUM
because 4 + 21 = 25
SUBSET-SUM is in NP
Theorem: SUBSET-SUM ∈ NP.
Proof 1: We construct a polynomial-time verifier V for
SUBSET-SUM.
V = “On input <<S,t>,c>
1. Test whether c is a collection of numbers that sum to t.
2. Test whether S contains all numbers in c.
3. If both pass, accept; Otherwise, reject. “
SUBSET-SUM is in NP: Alternative Proof
Proof 2: We construct a polynomial NTM N that decides
SUBSET-SUM.
N = “On input <S,t>
1. Non-deterministically select subset c of numbers in S.
2. Test if c is a collection of numbers that sum to t.
3. If yes, accept; Otherwise, reject.”
coNP
Question: What about CLIQUE and SUBSET-SUM?
As with HAMPATH, we do not know if they are in NP.
These languages belong to coNP – languages whose
complement is in NP.
We do not know whether coNP is different from NP.
P vs. NP
• P = class of languages where membership can
be decided in polynomial time (quickly).
• NP = class of languages where membership
can be verified in polynomial time (quickly).
?
P = NP
?
NP
NP=P
P
One of the greatest unsolved problems in
theoretical Computer Science and Mathematics
Best known method -- brute force:
NP  EXPTIME =
nk
TIME(2 )
k
‫עיתון הארץ ‪29.5.00‬‬