BU CS 332 – Theory of Computation
Lecture 20:
• More on NP
Reading:
Sipser Ch 7.3-7.5
Mark Bun April 13, 2020
Goals of complexity theory
Ultimate goal: Classify problems according to their feasibility and inherent computational difficulty
P ≈ Decision problems which can be solved efficiently
Can we exhibit general classes of problems which are either in
P or provably not in P?
Some problems provably require exponential time! (Chapter 9)
NP: A fundamental and practically important class of problems which have defied classification, but nevertheless exhibits important structure (NP completeness)
4/13/2020 CS332 – Theory of Computation 2
Nondeterministic Time and NP
4/13/2020 CS332 – Theory of Computation 3
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/13/2020 CS332 – Theory of Computation 4
Deterministic vs. nondeterministic time
Deterministic
Nondeterministic
𝒕𝒕(𝒏𝒏)
reject
accept
accept
accept or reject
reject
reject
4/13/2020
CS332 – Theory of Computation
5
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/13/2020
CS332 – Theory of Computation 6
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/13/2020 CS332 – Theory of Computation
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 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/13/2020 CS332 – Theory of Computation 8
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/13/2020 CS332 – Theory of Computation 9
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/13/2020 CS332 – Theory of Computation 10
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/13/2020 CS332 – Theory of Computation 11
Complexity class NP
Definition: NP is the class of languages decidable in
polynomial time on a nondeterministic TM
NP = ⋃∞ NTIME(𝑛𝑛𝑘𝑘) 𝑘𝑘=1
4/13/2020 CS332 – Theory of Computation 12
Hamiltonian Path
𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 = 𝐺𝐺, 𝑠𝑠, 𝑡𝑡 𝐺𝐺 is a directed graph and there
is a path from 𝑠𝑠 to 𝑡𝑡 that passes through every vertex exactly once}
𝑠𝑠𝑡𝑡
4/13/2020 CS332 – Theory of Computation 13
𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 ∈ NP
The following nondeterministic algorithm accepts in time 𝑂𝑂 𝑛𝑛1.5 , 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/13/2020 CS332 – Theory of Computation 14
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/13/2020 CS332 – Theory of Computation 15
𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻 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/13/2020 CS332 – Theory of Computation 16
NP is the class of languages with polynomial- time verifiers
Theorem: A language 𝐿𝐿 ∈ NP iff there is a polynomial- time verifier for 𝐿𝐿
Proof:
4/13/2020 CS332 – Theory of Computation 17
4/13/2020 CS332 – Theory of Computation 18
Examples of NP languages: SAT
“Is there an assignment to the variables in a logical
formula that make it evaluate to true?”
• Boolean variable: Variable that can take on the value
true/false (encoded as 0/1)
• Boolean operations: ∧ AND , ∨ OR , ¬ (NOT)
• Boolean formula: Expression made of Boolean variables and operations. Ex: (𝑥𝑥 ∨ 𝑥𝑥 ) ∧ 𝑥𝑥
123
• An assignment of 0s and 1s to the variables satisfies a formula 𝜑𝜑 if it makes the formula evaluate to 1
• A formula 𝜑𝜑 is satisfiable if there exists an assignment that satisfies it
4/13/2020 CS332 – Theory of Computation 19
Examples of NP languages: SAT
Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥3 Satisfiable?
Ex: (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ (𝑥𝑥1 ∨ 𝑥𝑥2) ∧ 𝑥𝑥2 Satisfiable? 𝑆𝑆𝐴𝐴𝐻𝐻 = { 𝜑𝜑 |𝜑𝜑 is a satisfiable formula}
Claim: 𝑆𝑆𝐴𝐴𝐻𝐻 ∈ NP
4/13/2020 CS332 – Theory of Computation 20
Examples of NP languages: TSP
“Given a list of cities and distances between them, is
there a ‘short’ tour of all of the cities?”
• A number of cities 𝑚𝑚
More precisely: Given
• A function 𝐷𝐷: {1, … , 𝑚𝑚} 2 → N giving the distance between each pair of cities
• A distance bound 𝐵𝐵
𝐻𝐻𝑆𝑆𝐻𝐻 = { 𝑚𝑚, 𝐷𝐷, 𝐵𝐵 |∃ a tour visiting every city
with length ≤ 𝐵𝐵}
4/13/2020 CS332 – Theory of Computation 21
P vs. NP
Question: Does P = NP?
Philosophically: Can every problem with an efficiently verifiable solution also be solved efficiently?
A central problem in mathematics and computer science
EXP
NP
EXP
P
P = NP
If P=NP
If P≠NP 4/13/2020
CS332 – Theory of Computation 22
A world where P = NP
• Many important decision problems can be solved in
polynomial time (𝐻𝐻𝐴𝐴𝑀𝑀𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻, 𝑆𝑆𝐴𝐴𝐻𝐻, 𝐻𝐻𝑆𝑆𝐻𝐻, etc.)
• Many search problems can be solved in polynomial time
(e.g., given a natural number, find a prime factorization)
• Many optimization problems can be solved in polynomial time (e.g., find the lowest energy conformation of a protein)
4/13/2020 CS332 – Theory of Computation 23
A world where P = NP
• Secure cryptography becomes impossible
An NP search problem: Given a ciphertext 𝐶𝐶, find a plaintext 𝑚𝑚 and encryption key 𝑘𝑘 that would encrypt to 𝐶𝐶
• AI / machine learning become easy: Identifying a consistent classification rule is an NP search problem
• Finding mathematical proofs becomes easy: NP search problem: Given a mathematical statement 𝑆𝑆 and length bound 𝑘𝑘, is there a proof of 𝑆𝑆 with length at most 𝑘𝑘?
General consensus: P ≠ NP
4/13/2020 CS332 – Theory of Computation 24
NP Completeness
4/13/2020 CS332 – Theory of Computation 25
What about a world where P ≠ NP Believe this to be true, but very far from proving it
P ≠ NP implies that there is a problem in NP which cannot be solved in polynomial time, but it might not be a useful one
Question: What would P ≠ NP allow us to conclude about problems we care about?
Idea: Identify the “hardest” problems in NP Find𝐿𝐿∈NPsuchthat𝐿𝐿∈P iff P=NP
4/13/2020 CS332 – Theory of Computation 26
Recall: Mapping reducibility
A function 𝑓𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.
Definition:
Definition:
Language 𝐴𝐴 is mapping reducible to language 𝐵𝐵, written
𝐴𝐴 ≤m 𝐵𝐵
if there is a computable function 𝑓𝑓: Σ∗ → Σ∗ such that for
all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵
4/13/2020 CS332 – Theory of Computation 27
Polynomial-time reducibility
A function 𝑓𝑓: Σ∗ → Σ∗ is polynomial-time computable if there is a polynomial-time TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.
Definition:
Definition:
Language 𝐴𝐴 is polynomial-time mapping reducible to
language 𝐵𝐵, written
if there is a polynomial-time computable function 𝑓𝑓: Σ∗ → Σ∗
𝐴𝐴 ≤p 𝐵𝐵
such that for all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵 4/13/2020 CS332 – Theory of Computation 28
Implications of poly-time reducibility
Theorem:If𝐴𝐴≤p 𝐵𝐵and𝐵𝐵∈𝐻𝐻,then𝐴𝐴∈𝐻𝐻 Proof:
4/13/2020 CS332 – Theory of Computation 29