6.045: Automata,ComputabilityandComplexity                                                                Spring2019

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 conondeterminism. Namely, we define AFAs (All-Paths Finite Automata) analogously to NFAs, except a string is accepted if and only if all possible computation paths in the AFA lead to an accept state (instead of some computation path, as in NFAs).

For simplicity, we define an AFA A = (Q, Σ, δ, Q0, F ) analogously to NFAs, except we require that for every state q  Q and every σ  Σ, δ(q, σ) =   .  That is, for every state and symbol there is at least one transition in the AFA. Also for simplicity, let’s make δ  : Q    Σ     2Q; that is, there are no ε-transitions in an AFA. We  say that an AFA    A = (Q, Σ, δ, Q0, F ) accepts w  = w1    wn (where wi    Σ for all i) if for all sequences r0, . . . , rn    Q such that r0 Q0 and ri+1  δ(ri, wi), we also have rn  F . That is, every valid computation path in the AFA leads to a final state.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) | tt is a directed graph with a Hamiltonian path from s to t}

is NP-complete. A Hamiltonian cycle in a graph is a cycle which includes each vertex exactly once. Prove that

                   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 k, decide if tt has a cycle of weight at most k which visits every vertex. That is

   TSP = {(tt, k) | tt is a weighted directed graph with a cycle of length at most k containing every vertex of 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 (tt, k, d, s, t) such that no matter how you add k edges to tt, the longest simple path from s to t in the resulting graph always has length less than d. Such graphs tt are “resilient” to having long paths. Prove that RESILIENT is coNP-complete.

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

5 Minimum Weight Assignments (6 points)

Suppose φ is a boolean formula on n variables x1, . . . , xn, and let α 0, 1 n be a variable assignment to x1, . . . , xn. The 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 n be the set of all variable assignments that satisfy φ, 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 ∈ PNP.

6 Minimum Formulas (3 points)

In this problem, we will see how P = NP implies more than just efficient algorithms for NP problems: it also implies efficient algorithms for some problems that are not known to be in 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 minimal formula if there is no formula ψ 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 NP, in coNP, or even in PNP ; it seems to be even harder! Prove that if P = NP then MIN-FORMULA is in P.

7 NP-Hardness vs NP-Completeness (8 points)

This problem is meant to illustrate the differences between being in NP, being NP-hard, and being NP-complete.

(a) (2 points) Show that AT M is NP-hard. Therefore, there is a language L which is NP-hard but not in NP.

(b) (5 points) Show that there exists a decidable language L which is NP-hard but is (provably) not in NP. Here is a suggested proof outline:

– Find a function t(n) such that NP ⊂ TIME[t(n)] but NP ƒ= TIME[t(n)].

– Find a language L such that for every Lj ∈ TIME[t(n)], Lj ≤p L.

– Show that if L ∈ NP, then TIME[t(n)] = NP.

(c) (1 point) Show that there exists a language L which is in NP but which is not NP-hard.