CS代考计算机代写 algorithm BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation
Lecture 22:
• NP‐Completeness Example • Space Complexity
• Savitch’s Theorem
Reading:
Sipser Ch 8.1‐8.2
Mark Bun April 22, 2020

NP‐completeness
Definition: A language is NP‐complete if 1) and
2) Every language
is poly‐time reducible to is NP‐hard”)
Theorem: If language , then
􏶍 for some NP‐complete is also NP‐complete
4/22/2020
CS332 ‐ Theory of Computation 2
, i.e.,
􏶍 (“ and

(3‐CNF Satisfiability)
Definition(s):
• A literal either a variable of its negation 􏶎 , 􏶏
• A clause is a disjunction (OR) of literals Ex.
• A 3‐CNF is a conjunction (AND) of clauses where each
clause contains exactly 3 literals Ex. 􏵶 􏶊 … 􏶐
􏶎􏶏􏶊􏶋􏶑􏵶 􏵶􏵶􏵶
Cook‐Levin Theorem: is NP‐complete
4/22/2020 CS332 ‐ Theory of Computation 3
􏶎􏶏􏶊

4/22/2020 CS332 ‐ Theory of Computation 4

Some general reduction strategies
• Reduction by simple equivalence
Ex. 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 􏶣 𝑆𝐸𝑇 􏶕􏶍 𝑉𝐸𝑅𝑇𝐸𝑋 􏶣 𝐶𝑂𝑉𝐸𝑅
and 𝑉𝐸𝑅𝑇𝐸𝑋 􏶣 𝐶𝑂𝑉𝐸𝑅 􏶕􏶍 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 􏶣 𝑆𝐸𝑇 • Reduction from special case to general case
Ex. 𝑉𝐸𝑅𝑇𝐸𝑋 􏶣 𝐶𝑂𝑉𝐸𝑅 􏶕􏶍 𝑆𝐸𝑇 􏶣 𝐶𝑂𝑉𝐸𝑅 • Gadget reductions
Ex. 3𝑆𝐴𝑇 􏶕􏶍 𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 􏶣 𝑆𝐸𝑇
4/22/2020 CS332 ‐ Theory of Computation 5

Independent Set
An independent set in an undirected graph 𝐺 is a set of vertices that includes at most one endpoint of every edge.
𝐼𝑁𝐷𝐸𝑃𝐸𝑁𝐷𝐸𝑁𝑇 􏶣 𝑆𝐸𝑇
􏵼 𝐺, 𝑘 𝐺 is an undirected graph containing an independent set with 􏶖 𝑘 vertices􏶤
• Is there an independent set of size  6?
• Yes.
• Is there an independent set of size  7?
• No.
independent set
4/22/2020 CS332 ‐ Theory of Computation 6

Independent Set is NP‐complete
1)
2) Reduce
Proof. “On input 𝜑 , where 𝜑 is a 3CNF formula,
1.
Construct graph 𝐺 from 𝜑
2.
Output 𝐺, 𝑘 , where 𝑘 is the number of clauses in 𝜑.”
4/22/2020 CS332 ‐ Theory of Computation 7
􏶍
• 𝐺 contains 3 vertices for each clause, one for each literal. • Connect 3 literals in a clause in a triangle.
• Connect literal to each of its negations.

Example of the reduction
𝜑􏵼 𝑥􏵶∨𝑥􏶊∨𝑥􏶋 ∧ 𝑥􏵶∨𝑥􏶊∨𝑥􏶋 ∧ 𝑥􏵶∨𝑥􏶊∨𝑥􏶑
4/22/2020 CS332 ‐ Theory of Computation 8

Proof of correctness for reduction
Let 𝑘 = # clauses and 𝑙 = # literals in 𝜑
Claim: 𝜑 is satisfiable iff 𝐺 has an ind. set of size 𝑘
⟹ Given a satisfying assignment, select one literal from each triangle. This is an ind. set of size 𝑘
⟸ Let 𝑆 be an ind. set of size 𝑘
• 𝑆 must contain exactly one vertex in each triangle
• Set these literals to true, and set all other variables in an arbitrary way
• Truth assignment is consistent and all clauses satisfied
Runtime: 𝑂􏶒𝑘 􏵷 𝑙􏶊􏶓 which is polynomial in input size
4/22/2020 CS332 ‐ Theory of Computation 9

Space Complexity
4/22/2020 CS332 ‐ Theory of Computation 10

Complexity measures we’ve studied so far
• Deterministic time TIME
• Nondeterministic time NTIME • Classes P, NP
Many other resources of interest:
Space (memory), randomness, parallel runtime / #processors, quantum entanglement, interaction, communication, …
4/22/2020 CS332 ‐ Theory of Computation 11

Space analysis
Space complexity of a TM (algorithm) = maximum number of tape cell it uses on a worst‐case input
Formally: Let ∗ . A TM every input , halts on
runs in space
if on cells
For nondeterministic machines:
runs in space
,
cells on every computational branch
using at most
4/22/2020
CS332 ‐ Theory of Computation 12
Let ∗ if on every input
. An NTM halts on
using at most

Space complexity classes
Let
A language
tape (deterministic) TM
if there exists a basic single‐ that
1) Decides , and 2) Runs in space
A language
tape nondeterministic TM
if there exists a single‐ that
1) Decides , and 2) Runs in space
4/22/2020 CS332 ‐ Theory of Computation 13

Example: Space complexity of SAT
Theorem:
Proof: The following deterministic TM decides linear space
using
On input where is a Boolean formula:
1. For each truth assignment to the variables
􏵶 􏶐of:
2. Evaluate on
3. If any evaluation , accept. Else, reject.
􏵶􏶐
4/22/2020 CS332 ‐ Theory of Computation 14

Example: NFA analysis
Theorem: Let
Then 􏶥􏵾􏵿
Proof: The following NTM decides
∗ 􏶥􏵾􏵿 in linear space
On input where is an NTM:
1. 2. 3. 4. 5.
Place a marker on the start state of .
Repeat 􏶦 times where is the # of states of :
􏶥􏵾􏵿
Nondeterministically select .
.
Adjust the markers to simulate all ways for
Accept if at any point none of the markers are on an accept state. Else, reject.
4/22/2020 CS332 ‐ Theory of Computation 15
to read

Example
0,1
1ε203 1
4/22/2020 CS332 ‐ Theory of Computation 16

Space vs. Time
4/22/2020 CS332 ‐ Theory of Computation 17

Space vs. Time
How about the opposite direction? Can low‐space algorithms be simulated by low‐time algorithms?
4/22/2020 CS332 ‐ Theory of Computation 18

Reminder: Configurations
A configuration is a string where
• Tape contents = (followed by blanks • Current state =
• Tape head on first symbol of
and )
∗
Example:
􏶎
Start configuration: Accepting configuration: = Rejecting configuration: =
4/22/2020 CS332 ‐ Theory of Computation
19
􏵹
􏶧􏶨􏶨􏶩􏶍􏶪
􏶫􏶩􏶬􏶩􏶨􏶪

Reminder: Configurations
Consider a TM with
• states
• tape alphabet
• space
How many configurations are possible when this TM is run on
an input
􏵳
Observation: If a TM enters the same configuration twice when run on input it loops forever
Corollary: A TM running in space also runs in time 􏶜􏶭􏵳
4/22/2020 CS332 ‐ Theory of Computation 20

Savitch’s Theorem
4/22/2020 CS332 ‐ Theory of Computation 21

Savitch’s Theorem: Deterministic vs. Nondeterministic Space
Theorem: Let be a function with 􏶊 . Then
4/22/2020 CS332 ‐ Theory of Computation
22