# 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