**6.045: Automata,ComputabilityandComplexity** Spring2019

**6.045: Automata,ComputabilityandComplexity**

### Problem Set #8 Due Date: Wednesday, May 8, 11:59pm

** Rules: **Same as before!

### 1 Conondeterminism and Finite Automata (6 points)

In this question, we study what happens to finite automata when we replace * nondeterminism *with the (apparently) stronger power of

*. Namely, we define AFAs (*

*conondeterminism**Finite Automata) analogously to NFAs, except a string is accepted if and only if*

*All-Paths**possible computation paths in the AFA lead to an accept state (instead of*

*all**computation path, as in NFAs).*

*some*For simplicity, we define an AFA * A *= (

*Σ*

*Q,*

*, δ, Q*_{0}

*) analogously to NFAs,*

*, F**we require that for every state*

*except**and every*

*q Q**Σ,*

*σ**(*

*δ**) = . That is, for every state and symbol there is at least one transition in the AFA. Also for simplicity, let’s make*

*q, σ**:*

*δ**Σ 2*

*Q**; that is, there are no*

^{Q}*-transitions in an AFA. We say that an AFA*

*ε**= (*

*A**Σ*

*Q,*

*, δ, Q*_{0}

*)*

*, F**=*

*accepts w*

*w*_{1}

*(where*

*w*_{n}*Σ for all*

*w*_{i}*) if for*

*i**sequences*

*all*

*r*_{0}

*such that*

*, . . . , r*_{n}*Q*

*r*_{0}

*Q*_{0}and

*r*_{i}_{+1}

*(*

*δ**), we also have*

*r*_{i}*, w*_{i}*. That is,*

*r*_{n}*F***valid computation path in the AFA leads to a final state.**

**every****Prove or disprove: the class of languages recognized by AFAs equals the class of regular languages.**

**2 More Hamiltonicity (2 points)**

We saw in lecture that

HAMPATH = * {*(

*)*

*tt, s, t**is a directed graph with a Hamiltonian path from*

*| tt**to*

*s*

*t}*is ** NP**-complete. A Hamiltonian cycle in a graph is a

*which includes each vertex exactly once. Prove that*

*cycle* HAMCYCLE = * {tt | tt *is a directed graph with a Hamiltonian cycle

*}.*is ** NP**-complete.

### 3 Traveling Salesperson Problem (2 points)

The Traveling Salesperson Problem is the problem of given a weighted directed graph * tt *and an integer

*, decide if*

*k**has a cycle of weight at most*

*tt**which visits every vertex. That is*

*k* TSP = * {*(

*)*

*tt, k**is a weighted directed graph with a cycle of length at most*

*| tt**containing every vertex of*

*k*

*tt}.*Prove that TSP is NP-complete.

### 4 Fun with coNP (5 points)

**(a) (4 points) **Let RESILIENT be the set of inputs of the form (

*) such that no matter how you add*

*tt, k, d, s, t**edges to*

*k**, the longest simple path from*

*tt**to*

*s**in the resulting graph always has length less than*

*t**. Such graphs*

*d**are “resilient” to having long paths. Prove that RESILIENT is*

*tt***-complete.**

**coNP****(b) (1 point) **Recall the language FACTORING from lecture. What would the consequences be for complexity theory, if we could show that FACTORING is

**-hard?**

**coNP****5 Minimum Weight Assignments (6 points)**

Suppose * φ *is a boolean formula on

*variables*

*n*

*x*_{1}

*, and let*

*, . . . , x*_{n}*0*

*α**1*

*,**be a variable assignment to*

^{n}

*x*_{1}

*. The*

*, . . . , x*_{n}*(*

*weight w**) is defined to be the number of 1’s in*

*α**. In other words, the weight of*

*α**is the number of variables in*

*α**which are assigned to be true.*

*α*Let * SA*(

*) 0*

*φ**1*

*,**be the set of all variable assignments that satisfy*

^{n}*, and let*

*φ**(*

*m**) := min*

*φ*

_{α∈SA}_{(}

_{φ}_{)}

*(*

*w**). Intuitively,*

*α**(*

*m**) is the minimum weight over all satisfying assignments to*

*φ**.*

*φ***(a) (4 points) **Define

LOW-WEIGHT-2SAT = * {*(

*)*

*φ, k**is a satisfiable 2-cnf formula such that*

*| φ**(*

*m**)*

*φ*

*≤ k}.*Prove that LOW-WEIGHT-2SAT is ** NP**-complete.

**(b) (2 points) **Define

MIN-WEIGHT-SAT = * {*(

*)*

*φ, k**is a satisfiable boolean formula such that*

*| φ**(*

*m**) =*

*φ*

*k} .*Show that MIN-WEIGHT-SAT *∈ *** P^{NP}**.

### 6 Minimum Formulas (3 points)

In this problem, we will see how ** P **=

**implies more than just efficient algorithms for**

**NP****problems: it also implies efficient algorithms for some problems that are**

**NP***to be in*

*not known***!**

**NP**Recall from lecture that two Boolean formulas are * equivalent *if they are defined over the same set of variables and they have the same output value on every variable assignment. Fix a binary encoding of formulas. A formula

*is a*

*φ**formula if there is no formula*

*minimal**with a smaller encoding length that is equivalent to*

*ψ**. Define*

*φ* MIN-FORMULA = * {φ | φ *is minimal

*}.*We noted in class that this problem is ** not **known to be in

**, in**

**NP****, or even in**

**coNP**

**P***; it seems to be even harder! Prove that if*

^{NP}**=**

**P****then MIN-FORMULA is in**

**NP****.**

**P**### 7 NP-Hardness vs NP-Completeness (8 points)

This problem is meant to illustrate the differences between being in ** NP**, being

**-hard, and being**

**NP****-complete.**

**NP****(a) (2 points) **Show that

*is*

*A*_{T}_{M}**-hard. Therefore, there is a language**

**NP***which is*

*L***-hard but not in**

**NP****.**

**NP****(b) (5 points) **Show that there exists a

*language*

*decidable**which is*

*L***-hard but is (provably) not in**

**NP****. Here is a suggested proof outline:**

**NP****– **Find a function * t*(

*) such that*

*n*

**NP***TIME[*

*⊂**(*

*t**)] but*

*n*

**NP***= TIME[*

*ƒ**(*

*t**)].*

*n***– **Find a language * L *such that for every

*TIME[*

*L*^{j}*∈**(*

*t**)],*

*n**.*

*L*^{j}*≤*_{p}*L***– **Show that if *L ∈ *** NP**, then TIME[

*(*

*t**)] =*

*n***.**

**NP****(c) (1 point) **Show that there exists a language

*which is in*

*L***but which is not**

**NP****-hard.**

**NP**