PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 22:
• Nondeterministic time, NP
• NP-completeness
Reading:
Sipser Ch 7.3-7.4
Mark Bun
April 14, 2021
Big-Oh, formally
𝑓 𝑛 = 𝑂(𝑔 𝑛 ) means:
There exist constants 𝑐 > 0, 𝑛0 > 0 such that
𝑓 𝑛 ≤ 𝑐𝑔 𝑛 for every 𝑛 ≥ 𝑛0
Example: Show that 7𝑛2 ⋅ 3𝑛 = 2𝑂 𝑛
4/14/2021 CS332 – Theory of Computation 2
Big-Oh, formally
𝑓 𝑛 = 𝑂(𝑔 𝑛 ) means:
There exist constants 𝑐 > 0, 𝑛0 > 0 such that
𝑓 𝑛 ≤ 𝑐𝑔 𝑛 for every 𝑛 ≥ 𝑛0
Example: Show that 7𝑛2 ⋅ 3𝑛 = 2𝑂 𝑛
4/14/2021 CS332 – Theory of Computation 3
Nondeterministic time
Let 𝑓 ∶ ℕ → ℕ
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/14/2021 CS332 – Theory of Computation 4
Complexity class NP
Definition: NP is the class of languages decidable in
polynomial time on a nondeterministic TM
NP = 𝑘=1ڂ
∞ NTIME(𝑛𝑘)
4/14/2021 CS332 – Theory of Computation 5
𝐻𝐴𝑀𝑃𝐴𝑇𝐻 ∈ NP
𝐻𝐴𝑀𝑃𝐴𝑇𝐻 = 𝐺, 𝑠, 𝑡 𝐺 is a directed graph and there
is a path from 𝑠 to 𝑡 that passes
through every vertex exactly once}
On input 𝐺, 𝑠, 𝑡 :
1. Nondeterministically guess a sequence of vertices
2. Check that the guess forms a Hamiltonian path
from 𝑠 to 𝑡
4/14/2021 CS332 – Theory of Computation 6
𝑠 𝑡
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
Running time of a verifier is only measured in terms of 𝑤
𝑉 is a polynomial-time verifier if it runs in time polynomial
in |𝑤| on every input 𝑤, 𝑐
(Without loss of generality, |𝑐| is polynomial in |𝑤|, i.e.,
𝑐 = 𝑂(|𝑤|𝑘) for some constant 𝑘)
4/14/2021 CS332 – Theory of Computation 7
𝐻𝐴𝑀𝑃𝐴𝑇𝐻 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. Check that 𝑐1 = 𝑠, 𝑐𝑘 = 𝑡, and there is an edge
from every 𝑐𝑖 to 𝑐𝑖+1
3. Accept if all checks pass, otherwise, reject.
4/14/2021 CS332 – Theory of Computation 8
NP is the class of languages with polynomial-
time verifiers
Theorem: A language 𝐿 ∈ NP iff there is a polynomial-
time verifier for 𝐿
Proof: ⇐ Let 𝐿 have a poly-time verifier 𝑉( 𝑤, 𝑐 )
Idea: Design NTM 𝑁 for 𝐿 that nondeterministically
guesses a certificate
4/14/2021 CS332 – Theory of Computation 9
NP is the class of languages with polynomial-
time verifiers
⇒ Let 𝐿 be decided by an NTM 𝑁 making up to 𝑏
nondeterministic choices in each step
Idea: Design verifier 𝑉 for 𝐿 where certificate is sequence
of “good” nondeterministic choices
4/14/2021 CS332 – Theory of Computation 10
Alternative proof of NP ⊆ EXP
One can prove NP ⊆ EXP as follows. Let 𝑉 be a verifier for a
language 𝐿 running in time 𝑇(𝑛). We can construct a
2𝑂 𝑇 𝑛 time algorithm for 𝐿 as follows.
a) On input 〈𝑤, 𝑐〉, run 𝑉 on 〈𝑤, 𝑐〉 and output the result
b) On input 𝑤, run 𝑉 on all possible 〈𝑤, 𝑐〉, where 𝑐 is a
certificate. Accept if any run accepts.
c) On input 𝑤, run 𝑉 on all possible 〈𝑤, 𝑐〉, where 𝑐 is a
certificate of length at most 𝑇 𝑤 . Accept if any run
accepts.
d) On input 𝑤, run 𝑉 on all possible 〈𝑥, 𝑐〉, where 𝑥 is a string
of length |𝑤| and 𝑐 is a certificate of length at most
𝑇 𝑤 . Accept if any run accepts.
4/14/2021 CS332 – Theory of Computation 11
WARNING: Don’t mix-and-match the NTM and
verifier interpretations of NP
To show a language 𝐿 is in NP, do exactly one:
1) Exhibit a poly-time NTM for 𝐿
𝑁 = “On input 𝑥:
OR
2) Exhibit a poly-time (deterministic) verifier for 𝐿
𝑉 = “On input 𝑥 and certificate 𝑐:
4/14/2021 CS332 – Theory of Computation 12
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: (𝑥1 ∨ 𝑥2) ∧ 𝑥3
• 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/14/2021 CS332 – Theory of Computation 13
Examples of NP languages: SAT
Ex: (𝑥1 ∨ 𝑥2) ∧ 𝑥3 Satisfiable?
Ex: (𝑥1 ∨ 𝑥2) ∧ 𝑥1 ∧ 𝑥2 Satisfiable?
𝑆𝐴𝑇 = { 𝜑 |𝜑 is a satisfiable formula}
Claim: 𝑆𝐴𝑇 ∈ NP
4/14/2021 CS332 – Theory of Computation 14
Examples of NP languages: Traveling
Salesperson
“Given a list of cities and distances between them, is
there a ‘short’ tour of all of the cities?”
More precisely: Given
• A number of cities 𝑚
• A function 𝐷: {1, … ,𝑚} 2→ ℕ giving the distance
between each pair of cities
• A distance bound 𝐵
𝑇𝑆𝑃 = { 𝑚,𝐷, 𝐵 |∃ a tour visiting every city
with length ≤ 𝐵}
4/14/2021 CS332 – Theory of Computation 15
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
4/14/2021 CS332 – Theory of Computation 16
EXP NP
P
If P NP If P = NP
EXP
P = NP
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/14/2021 CS332 – Theory of Computation 17
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/14/2021 CS332 – Theory of Computation 18
NP-Completeness
4/14/2021 CS332 – Theory of Computation 19
Understanding the P vs. NP question
Believe P ≠ NP, but very far from proving it
Question 1: How can studying specific computational
problems help us get a handle on resolving P vs. NP?
Question 2: What would P ≠ NP allow us to conclude
about specific problems we care about?
Idea: Identify the “hardest” problems in NP
Find 𝐿 ∈ NP such that 𝐿 ∈ P iff P = NP
4/14/2021 CS332 – Theory of Computation 20
Recall: Mapping reducibility
Definition:
A function 𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀
which, given as input any 𝑤 ∈ Σ∗, halts with only 𝑓(𝑤) on
its tape.
Definition:
Language 𝐴 is mapping reducible to language 𝐵, written
𝐴 ≤m 𝐵
if there is a computable function 𝑓: Σ∗ → Σ∗ such that for
all strings 𝑤 ∈ Σ∗, we have 𝑤 ∈ 𝐴⟺ 𝑓(𝑤) ∈ 𝐵
4/14/2021 CS332 – Theory of Computation 21
Polynomial-time reducibility
Definition:
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:
Language 𝐴 is polynomial-time reducible to language 𝐵,
written
𝐴 ≤p 𝐵
if there is a polynomial-time computable function 𝑓: Σ∗ → Σ∗
such that for all strings 𝑤 ∈ Σ∗, we have 𝑤 ∈ 𝐴⟺ 𝑓(𝑤) ∈ 𝐵
4/14/2021 CS332 – Theory of Computation 22
Implications of poly-time reducibility
Theorem: If 𝐴 ≤p 𝐵 and 𝐵 ∈ P, then 𝐴 ∈ P
Proof: Let 𝑀 decide 𝐵 in poly time, and let 𝑓 be a poly-
time reduction from 𝐴 to 𝐵. The following TM decides 𝐴
in poly time:
4/14/2021 CS332 – Theory of Computation 23
Is NP closed under poly-time reductions?
If 𝐴 ≤p 𝐵 and 𝐵 is in NP, does that mean 𝐴 is also in NP?
a) Yes, the same proof works using NTMs instead of TMs
b) No, because the new machine is an NTM instead of a
deterministic TM
c) No, because the new NTM may not run in polynomial
time
d) No, because the new NTM may accept some inputs it
should reject
e) No, because the new NTM may reject some inputs it
should accept
4/14/2021 CS332 – Theory of Computation 24
NP-completeness
Definition: A language 𝐵 is NP-complete if
1) 𝐵 ∈ NP, and
2) Every language 𝐴 ∈ NP is poly-time reducible to
𝐵, i.e., 𝐴 ≤p 𝐵 (“𝐵 is NP-hard”)
4/14/2021 CS332 – Theory of Computation 25
Implications of NP-completeness
Theorem: Suppose 𝐵 is NP-complete.
Then 𝐵 ∈ P iff P = NP
Proof:
4/14/2021 CS332 – Theory of Computation 26
Implications of NP-completeness
Theorem: Suppose 𝐵 is NP-complete.
Then 𝐵 ∈ P iff P = NP
Consequences of 𝐵 being NP-complete:
1) If you want to show P = NP, you just have to show
𝐵 ∈ P
2) If you want to show P ≠ NP, you just have to show
𝐵 ∉ P
3) If you already believe P ≠ NP, then you believe 𝐵 ∉ P
4/14/2021 CS332 – Theory of Computation 27