BU CS 332 – Theory of Computation
Lecture 19: • More on P
Reading:
Sipser Ch 7.2‐7.3
• Nondeterministic time, NP
Mark Bun April 8, 2020
First topic: Time complexity
Last time: Answering the basic questions
1. How do we measure complexity? (as in CS 330)
2. Asymptotic notation (as in CS 330)
3. How robust is the TM model when we care about measuring complexity?
4. How do we mathematically capture our intuitive notion of “efficient algorithms”?
4/8/2020 CS332 ‐ Theory of Computation 2
Running time and time complexity classes
Let
A TM runs in time if on every input , halts on within at most steps
is a class (i.e., set) of languages:
A language
tape (deterministic) TM that
1) Decides , and
2) Runs in time
if there exists a basic single‐
4/8/2020 CS332 ‐ Theory of Computation 3
Complexity Class
4/8/2020 CS332 ‐ Theory of Computation 4
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: Captures class of problems that are feasible to solve on computers
4/8/2020 CS332 ‐ Theory of Computation 5
A note about encodings
We’ll still use the notation for “any reasonable” encoding of the input to a TM…but now we have to be more careful about what we mean by “reasonable”
How long is the encoding of a ‐vertex graph… … as an adjacency matrix?
… as an adjacency list?
How long is the encoding of a natural number
… in binary? … in decimal?
… in unary?
4/8/2020 CS332 ‐ Theory of Computation 6
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/8/2020 CS332 ‐ Theory of Computation 7
Examples of languages in
• 𝑃𝐴𝑇𝐻 𝐺, 𝑠, 𝑡
𝐺 is a directed graph with a directed path from 𝑠 to 𝑡
• 𝐸
𝐷 𝐷 is a DFA that recognizes the empty language
4/8/2020
CS332 ‐ Theory of Computation 8
Examples of languages in
• •
4/8/2020
CS332 ‐ Theory of Computation 9
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
: by
Try to divide
If divides If all fail to divide
, accept , reject
How many divisions does this algorithm require in terms of ?
4/8/2020 CS332 ‐ Theory of Computation 10
CFG Generation
Theorem: Every context‐free language is in
Chomsky Normal Form for CFGs:
• Canhavearule𝑆 → 𝜀
• Allremainingrulesoftheform𝐴→𝐵𝐶or𝐴→𝑎 • Cannot have 𝑆 on the RHS of any rule
Lemma: Any CFG can be converted into an equivalent CFG in Chomsky Normal Form
Lemma: If is in Chomsky Normal Form, any nonempty string w that can be derived from has a derivation with at most steps
4/8/2020
CS332 ‐ Theory of Computation 11
CFG Generation
Theorem: Every context‐free language is in
Proof attempt: Let Form. Define a TM
be a CFL with a CFG recognizing :
in Chomsky Normal
On input : (Let
1. Enumerate all strings derivable in
2. If any of these strings equal , accept. Else, reject.
What is the running time of this algorithm?
A better idea: Use dynamic programming
‐ Identify subproblems
‐ Record solutions to subproblems in a table
)
‐ Solve bigger subproblems by combining solutions to smaller subproblems
4/8/2020 CS332 ‐ Theory of Computation 12
steps
4/8/2020 CS332 ‐ Theory of Computation 13
Examples of languages in
Problem
Description
Algorithm
Yes
No
MULTIPLE
Is x a multiple of y?
Grade school division
51, 17
51, 16
RELPRIME
Are x and y relatively prime? Is x prime?
Euclid (300 BCE) AKS (2002)
34, 39 53
34, 51
PRIMES
51
all CFLs
Is a given string in a fixed CFL?
Depends on
the
language;
e.g.
(([])[])
Depends on
the
language;
e.g.
([)], (()
(e.g. the language of balanced parentheses and brackets)
(E.g., is the string of parentheses and brackets balanced?)
Dynamic programming
LSOLVE
Isthereavectorxthat satisfiesAx=b?
Gauss-Edmonds elimination
1 0 0 1 1 1 1,1
4/8/2020
CS332 ‐ Theory of Computation
14
0 1 1 2
2 4 2, 4
031536 0111
Beyond polynomial time
Definition: is the class of languages decidable in exponential time on a basic single‐tape (deterministic) TM
4/8/2020
CS332 ‐ Theory of Computation 15
Nondeterministic Time and NP
4/8/2020 CS332 ‐ Theory of Computation 16
Nondeterministic time
Let
A NTM runs in time if on every input halts on within at most steps on every
,
computational branch
4/8/2020 CS332 ‐ Theory of Computation
17
Deterministic vs. nondeterministic time
Deterministic
Nondeterministic
accept or reject
reject reject
4/8/2020
CS332 ‐ Theory of Computation
18
𝒕𝒏
reject
accept
accept
Deterministic vs. nondeterministic time
Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in
Finite control
𝑤 ⊔
# 𝑤 3 7
𝑤
nondeterministic choices from tape 3) Address in computation tree
4/8/2020
CS332 ‐ Theory of Computation 19
time
Proof: Simulate NTM by 3‐tape TM
𝑤 𝑤 𝑤 𝑤
Input 𝑤 to 𝑁 (read‐only) Simulation tape (run 𝑁 on 𝑤 using
1 3
Deterministic vs. nondeterministic time
Theorem: Let be a function. Every NTM running in time has an equivalent single‐tape TM running in
time
input
Proof: Simulate NTM by 3‐tape TM • # leaves:
• # nodes:
Running time:
simulation address
To simulate one root‐to‐node path:
Total time:
4/8/2020 CS332 ‐ Theory of Computation
20
Deterministic vs. nondeterministic time
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
= ·=
4/8/2020 CS332 ‐ Theory of Computation 21