BU CS 332 – Theory of Computation
Lecture 19: • More on P
• Nondeterministic time, NP
Mark Bun April 8, 2020
Reading:
Sipser Ch 7.2-7.3
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𝑓𝑓∶ N→ N
A TM 𝑀𝑀 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛, 𝑀𝑀 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps
TIME(𝑓𝑓(𝑛𝑛)) is a class (i.e., set) of languages:
A language 𝐴𝐴 ∈ TIME(𝑓𝑓(𝑛𝑛)) if there exists a basic single-
tape (deterministic) TM 𝑀𝑀 that
1) Decides 𝐴𝐴, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/8/2020 CS332 – Theory of Computation 3
Complexity Class P
4/8/2020 CS332 – Theory of Computation 4
Complexity class P
Definition: P is the class of languages decidable in
polynomial time on a basic single-tape (deterministic) TM
P = ⋃∞ TIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1
• 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: poly(𝑛𝑛) executions of poly(𝑛𝑛)-time subroutines run on poly(𝑛𝑛)- size inputs gives an algorithm running in poly(𝑛𝑛) 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 P • 𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 =
𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph with a directed path from 𝑠𝑠 to 𝑡𝑡}
• 𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes the empty language} 4/8/2020 CS332 – Theory of Computation 8
Examples of languages in P
• 𝑅𝑅𝐸𝐸𝑅𝑅𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸 = 𝑥𝑥, 𝑦𝑦 𝑥𝑥 and 𝑦𝑦 are relatively prime}
• 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃 = 𝑥𝑥 𝑥𝑥 is prime}
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….
4/8/2020 CS332 – Theory of Computation 9
A polynomial-time algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃? Consider the following algorithm for 𝑃𝑃𝑅𝑅𝑅𝑅𝑀𝑀𝐸𝐸𝑃𝑃
On input 𝑥𝑥 : For𝑏𝑏=2,3,5,…, 𝑥𝑥:
Try to divide 𝑥𝑥 by 𝑏𝑏
If 𝑏𝑏 divides 𝑥𝑥, accept If all 𝑏𝑏 fail to divide 𝑥𝑥, 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 P
• Can have a rule 𝑃𝑃 → 𝜀𝜀
• Allremainingrulesoftheform𝐴𝐴→𝐵𝐵𝐵𝐵or𝐴𝐴→𝑎𝑎 • Cannot have 𝑃𝑃 on the RHS of any rule
Chomsky Normal Form for CFGs:
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 most2 𝑤𝑤 −1steps
4/8/2020 CS332 – Theory of Computation 11
Theorem: Every context-free language is in P
Proof attempt: Let 𝐴𝐴 be a CFL with a CFG 𝐺𝐺 in Chomsky Normal
CFG Generation
Form. Define a TM 𝑀𝑀 recognizing 𝐴𝐴:
On input 𝑤𝑤: (Let 𝑛𝑛 = |𝑤𝑤|)
1. Enumerate all strings derivable in ≤ 2𝑛𝑛 − 1 steps 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
4/8/2020 CS332 – Theory of Computation 13
Examples of languages in P
Problem
MULTIPLE
RELPRIME
PRIMES
all CFLs
(e.g. the language of balanced parentheses and brackets)
LSOLVE
Description
Is x a multiple of y?
Are x and y relatively prime?
Is x prime?
Is a given string in a fixed CFL?
(E.g., is the string of parentheses and brackets balanced?)
Is there a vector x that satisfies Ax = b?
Algorithm
Grade school division
Euclid (300 BCE)
AKS (2002)
Dynamic programming
Gauss-Edmonds elimination
Yes
51, 17
34, 39
53
No
51, 16
34, 51
51
Depends on
the
language;
e.g.
(([])[])
Depends on
the
language;
e.g.
([)], (()
01121001 2 4 −2 , 4 1 1 1 , 1 031536 0111
4/8/2020
CS332 – Theory of Computation 14
Beyond polynomial time
Definition: EXP is the class of languages decidable in exponential time on a basic single-tape (deterministic) TM
EXP = ⋃∞ TIME(2𝑛𝑛𝑘𝑘) 𝑘𝑘=1
4/8/2020 CS332 – Theory of Computation 15
Nondeterministic Time and NP
4/8/2020 CS332 – Theory of Computation 16
Nondeterministic time
Let𝑓𝑓∶ N→ N
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
𝒕𝒕(𝒏𝒏)
reject
accept
accept
accept or reject
reject
reject
4/8/2020
CS332 – Theory of Computation
18
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
Deterministic vs. nondeterministic time
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM
𝑤𝑤1 𝑤𝑤2 𝑤𝑤3 𝑤𝑤4
Input 𝑤𝑤 to 𝑁𝑁 (read-only) Simulation tape (run 𝑁𝑁 on 𝑤𝑤 using
nondeterministic choices from tape 3) Address in computation tree
Finite control
𝑤𝑤1 ⊔
𝑤𝑤3 𝑤𝑤4
#
4/8/2020
CS332 – Theory of Computation 19
1
3
3
7
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
Deterministic vs. nondeterministic time
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM 𝑀𝑀 • # leaves:
• # nodes:
Running time:
To simulate one root-to-node path:
Total time:
input simulation address
4/8/2020 CS332 – Theory of Computation
20
Theorem: Let 𝑡𝑡 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every NTM running in time 𝑡𝑡 𝑛𝑛 has an equivalent single-tape TM running in
Deterministic vs. nondeterministic time
time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
Proof: Simulate NTM by 3-tape TM in time 2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
We know that a 3-tape TM can be simulated by a single- tape TM with quadratic overhead, hence we get running
time
(2𝑂𝑂(𝑡𝑡 𝑛𝑛 ))2 =22�𝑂𝑂(𝑡𝑡 𝑛𝑛 ) =2𝑂𝑂(𝑡𝑡 𝑛𝑛 )
4/8/2020 CS332 – Theory of Computation 21
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/8/2020 CS332 – Theory of Computation 22
Nondeterministic time
Let𝑓𝑓∶ N→ N
A NTM 𝑀𝑀 runs in time 𝑓𝑓(𝑛𝑛) if on every input 𝑤𝑤 ∈ Σ𝑛𝑛,
𝑀𝑀 halts on 𝑤𝑤 within at most 𝑓𝑓(𝑛𝑛) steps on every computational branch
NTIME(𝑓𝑓(𝑛𝑛)) is a class (i.e., set) of languages:
A language 𝐴𝐴 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑀𝑀
that
1) Decides 𝐴𝐴, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/8/2020 CS332 – Theory of Computation 23
NTIME explicitly
A language 𝐴𝐴 ∈ NTIME(𝑓𝑓(𝑛𝑛)) if there exists an NTM 𝑀𝑀 such that, on every input 𝑤𝑤 ∈ Σ∗
1. Every computational branch of 𝑀𝑀 halts in either the
2. 3.
accept or reject state within 𝑓𝑓( 𝑤𝑤 ) steps
𝑤𝑤 ∈ 𝐴𝐴 iff there exists an accepting computational
branch of 𝑀𝑀 on input 𝑤𝑤
𝑤𝑤 ∉ 𝐴𝐴 iff every computational branch of 𝑀𝑀 rejects on
input 𝑤𝑤 (or dies with no applicable transitions)
4/8/2020 CS332 – Theory of Computation 24
Complexity class NP
Definition: NP is the class of languages decidable in
polynomial time on a nondeterministic TM
NP = ⋃∞ NTIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1
4/8/2020 CS332 – Theory of Computation 25
Hamiltonian Path
𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph and there
is a path from 𝑠𝑠 to 𝑡𝑡 that passes through every vertex exactly once}
𝑠𝑠𝑡𝑡
4/8/2020 CS332 – Theory of Computation 26
𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 ∈ NP
The following nondeterministic algorithm accepts in time 𝑂𝑂 𝑛𝑛3 , where 𝑛𝑛 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 , adjacency matrix encoding
On input 𝐺𝐺,𝑠𝑠,𝑡𝑡 : (Vertices of 𝐺𝐺 are numbers 1,…,𝑘𝑘) 1. Nondeterministically guess a sequence
𝑐𝑐 , 𝑐𝑐 ,…,𝑐𝑐 of numbers 1,…,𝑘𝑘
12𝑘𝑘
2. Check that 𝑐𝑐 , 𝑐𝑐 ,…,𝑐𝑐 is a permutation: Every 12𝑘𝑘
number 1, … , 𝑘𝑘 appears exactly once 3.Checkthat𝑐𝑐 =𝑠𝑠,𝑐𝑐 =𝑡𝑡,andthereisanedge
fromevery𝑐𝑐 to𝑐𝑐
𝑖𝑖 𝑖𝑖+1
1𝑘𝑘
4. Accept if all checks pass, otherwise, reject.
4/8/2020 CS332 – Theory of Computation 27
An alternative characterization of NP “Languages with polynomial-time verifiers”
A verifier for a language 𝑅𝑅 is a deterministic algorithm 𝑉𝑉 such that 𝑤𝑤 ∈ 𝑅𝑅 iff there exists a string 𝑐𝑐 such that
𝑉𝑉( 𝑤𝑤, 𝑐𝑐 ) accepts
Runningtimeofaverifierisonlymeasuredintermsof 𝑤𝑤 𝑉𝑉 is a polynomial-time verifier if it runs in time polynomial
in|𝑤𝑤|oneveryinput 𝑤𝑤,𝑐𝑐
(Without loss of generality, |𝑐𝑐| is polynomial in |𝑤𝑤|, i.e.,
𝑐𝑐 = 𝑂𝑂(|𝑤𝑤|𝑘𝑘) for some constant 𝑘𝑘)
4/8/2020 CS332 – Theory of Computation 28
𝑃𝑃𝐴𝐴𝑀𝑀𝑃𝑃𝐴𝐴𝑃𝑃𝑃𝑃 has a polynomial-time verifier Certificate 𝑐𝑐:
Verifier 𝑉𝑉:
On input 𝐺𝐺,𝑠𝑠,𝑡𝑡,𝑐𝑐 : (Vertices of 𝐺𝐺 are numbers 1,…,𝑘𝑘)
1. Check that 𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑘𝑘 is a permutation: Every number 1, … , 𝑘𝑘 appears exactly once
2.Checkthat𝑐𝑐1 =𝑠𝑠,𝑐𝑐𝑘𝑘 =𝑡𝑡,andthereisanedge from every 𝑐𝑐𝑖𝑖 to 𝑐𝑐𝑖𝑖+1
3. Accept if all checks pass, otherwise, reject.
4/8/2020 CS332 – Theory of Computation 29
NP is the class of languages with polynomial- time verifiers
Theorem: A language 𝑅𝑅 ∈ NP iff there is a polynomial- time verifier for 𝑅𝑅
Proof:
4/8/2020 CS332 – Theory of Computation 30