Microsoft PowerPoint – CS332-Lec22-ann
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 such that
for every
Example: Show that
4/14/2021 CS332 ‐ Theory of Computation 2
Big‐Oh, formally
means:
There exist constants such that
for every
Example: Show that
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
is a class (i.e., set) of languages:
A language if there exists an NTM
that
1) Decides , and
2) Runs in time
4/14/2021 CS332 ‐ Theory of Computation 4
Complexity class
Definition: is the class of languages decidable in
polynomial time on a nondeterministic TM
4/14/2021 CS332 ‐ Theory of Computation 5
𝐻𝐴𝑀𝑃𝐴𝑇𝐻 𝐺, 𝑠, 𝑡 𝐺 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
“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. Check that is a permutation: Every
number appears exactly once
2. Check that , , and there is an edge
from every to
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 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
One can prove as follows. Let be a verifier for a
language running in time . We can construct a
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
To show a language is in , 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 languages: SAT
“Is there an assignment to the variables in a logical
formula that make it evaluate to ?”
• Boolean variable: Variable that can take on the value
/ (encoded as 0/1)
• Boolean operations:
• Boolean formula: Expression made of Boolean variables
and operations. Ex:
• 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 languages: SAT
Ex: Satisfiable?
Ex: Satisfiable?
Claim:
4/14/2021 CS332 ‐ Theory of Computation 14
Examples of 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 giving the distance
between each pair of cities
• A distance bound
4/14/2021 CS332 ‐ Theory of Computation 15
vs.
Question: Does ?
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
• 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
• 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:
4/14/2021 CS332 ‐ Theory of Computation 18