Microsoft PowerPoint – CS332-Lec21-ann
BU CS 332 – Theory of Computation
Lecture 21:
• Complexity Class P
• Nondeterministic time, NP
Reading:
Sipser Ch 7.2, 7.3
Mark Bun
April 12, 2021
Complexity class
Definition: is the class of languages decidable in
polynomial time on a basic single‐tape (deterministic) TM
• Class doesn’t change if we substitute in another
reasonable deterministic model (Extended Church‐Turing)
• Cobham‐Edmonds Thesis: Roughly captures class of
problems that are feasible to solve on computers
4/12/2021 CS332 ‐ Theory of Computation 2
Describing and analyzing polynomial‐time
algorithms
• Due to Extended Church‐Turing Thesis, we can still use
high‐level descriptions on multi‐tape machines
• Polynomial‐time is robust under composition:
executions of ‐time subroutines run on ‐
size inputs gives an algorithm running in time.
Can freely use algorithms we’ve seen before as
subroutines if we’ve analyzed their runtime
• Need to be careful about size of inputs! (Assume inputs
represented in binary unless otherwise stated.)
4/12/2021 CS332 ‐ Theory of Computation 3
Examples of languages in
𝑃𝐴𝑇𝐻
𝐺, 𝑠, 𝑡 𝐺 is a directed graph with a directed path from 𝑠 to 𝑡
4/12/2021 CS332 ‐ Theory of Computation 4
Examples of languages in
4/12/2021 CS332 ‐ Theory of Computation 5
Examples of languages in
•
•
4/12/2021 CS332 ‐ Theory of Computation 6
2006 Gödel Prize citation
The 2006 Gödel Prize for outstanding articles
in theoretical computer science is awarded to
Manindra Agrawal, Neeraj Kayal, and Nitin
Saxena for their paper “PRIMES is in P.”
In August 2002 one of the most ancient
computational problems was finally solved….
A polynomial‐time algorithm for ?
Consider the following algorithm for
On input
For :
‐ Try to divide by
‐ If divides , accept
If all fail to divide , reject
How many divisions does this algorithm require in terms of
? a) b) c) d)
4/12/2021 CS332 ‐ Theory of Computation 7
Beyond polynomial time
Definition: is the class of languages decidable in
exponential time on a basic single‐tape (deterministic) TM
4/12/2021 CS332 ‐ Theory of Computation 8
Why study ?
Criticism of the Cobham‐Edmonds Thesis:
‐ Algorithms running in time aren’t really efficient
Response: Runtimes improve with more research
‐ Does not capture some physically realizable models using
randomness, quantum mechanics
Response: Randomness may not change , useful principles
4/12/2021 CS332 ‐ Theory of Computation 9
𝑇𝐼𝑀𝐸 𝑛 vs. 𝑇𝐼𝑀𝐸 𝑛 𝑃 vs. 𝐸𝑋𝑃
decidable vs.
undecidable
Nondeterministic Time
and NP
4/12/2021 CS332 ‐ Theory of Computation 10
Nondeterministic time
Let
A NTM runs in time if on every input ,
halts on within at most steps on every
computational branch
4/12/2021 CS332 ‐ Theory of Computation 11
Deterministic vs. nondeterministic time
4/12/2021 CS332 ‐ Theory of Computation 12
Deterministic Nondeterministic
accept or reject reject
accept
𝒕 𝒏
reject
accept
reject
Deterministic vs. nondeterministic time
4/12/2021 CS332 ‐ Theory of Computation 13
𝑤 𝑤 𝑤 𝑤
Finite
control
𝑤 ⊔ # 𝑤 𝑤
1 3 3 7
Input 𝑤 to 𝑁 (read‐only)
Simulation tape (run 𝑁 on 𝑤 using
nondeterministic choices from tape 3)
Address in computation tree
Theorem: Let be a function. Every NTM running
in time has an equivalent single‐tape TM running in
time
Proof: Simulate NTM by 3‐tape TM
Counting leaves
4/12/2021 CS332 ‐ Theory of Computation 14
What is the maximum number of leaves in a tree with
branching factor and depth ?
a)
b)
c)
d)
Deterministic vs. nondeterministic time
4/12/2021 CS332 ‐ Theory of Computation 15
Theorem: Let be a function. Every NTM running
in time has an equivalent single‐tape TM running in
time
Proof: Simulate NTM by 3‐tape TM
• # leaves:
Running time:
To simulate one root‐to‐leaf path:
Total time:
input
simulation
address
Deterministic vs. nondeterministic time
4/12/2021 CS332 ‐ Theory of Computation 16
Theorem: Let be a function. Every NTM running
in time has an equivalent single‐tape TM running in
time
Proof: Simulate NTM by 3‐tape TM in time
We know that a 3‐tape TM can be simulated by a single‐
tape TM with quadratic overhead, hence we get running
time
= · =
Difference in time complexity
Extended Church‐Turing Thesis:
At most polynomial difference in running time between all
(reasonable) deterministic models
At most exponential difference in running time between
deterministic and nondeterministic models
4/12/2021 CS332 ‐ Theory of Computation 17
Nondeterministic time
Let
A NTM runs in time if on every input ,
halts on within at most steps on every
computational branch
is a class (i.e., set) of languages:
A language if there exists an NTM
that
1) Decides , and
2) Runs in time
4/12/2021 CS332 ‐ Theory of Computation 18
NTIME explicitly
A language if there exists an NTM
such that, on every input ∗
1. Every computational branch of halts in either the
accept or reject state within steps
2. iff there exists an accepting computational
branch of on input
3. iff every computational branch of rejects on
input (or dies with no applicable transitions)
4/12/2021 CS332 ‐ Theory of Computation 19
Complexity class
Definition: is the class of languages decidable in
polynomial time on a nondeterministic TM
Which of the following are definitely true about ?
a)
b)
c)
d)
e)
4/12/2021 CS332 ‐ Theory of Computation 20
Hamiltonian Path
4/12/2021 CS332 ‐ Theory of Computation 21
The following nondeterministic algorithm decides
in polynomial time:
On input : (Vertices of are numbers )
1. Nondeterministically guess a sequence
of numbers
2. Check that is a permutation: Every
number appears exactly once
3. Check that , , and there is an edge
from every to
4. Accept if all checks pass, otherwise, reject.
4/12/2021 CS332 ‐ Theory of Computation 22
Analyzing the algorithm
Need to check:
1) Correctness
2) Running time
4/12/2021 CS332 ‐ Theory of Computation 23