﻿ theory of computation代写 boolean formula代写 Problem Set代写

# theory of computation代写 boolean formula代写 Problem Set代写

2021-03-03 17:58 星期三 所属： course代写 浏览：55 ## 6.045: Automata, ComputabilityandComplexity Spring 2019

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

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

Rules: Same as before!

### 1 Conondeterminism and Finite Automata (6points) theory of computation代写

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.theory of computation代写

Prove or disprove: the class of languages recognized by AFAs equals the class of regular languages. theory of computation代写

### 2.More Hamiltonicity (2points) theory of computation代写

We saw in lecture that HAMPATH = {(tt, s, t) | tt is a directed graph with a Hamiltonian path from s to tis 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 (2points)

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}.theory of computation代写

Prove that TSP is NP-complete.

### 4 Fun with coNP (5points)

(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 edgesto 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 iscoNP-hard?theory of computation代写

### 5 Minimum Weight Assignments (6points)

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.theory of computation代写

(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 (3points) theory of computation代写

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}.theory of computation代写

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 (8points)

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

(a)(2 points) Show that ATM is NP-hard. Therefore, there is a language L which is NP-hard but not in NP.theory of computation代写

(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 proofoutline:

Finda function t(n) such that NP  TIME[t(n)] but NP ƒ= TIME[t(n)].

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

Show that if L NP, then TIME[t(n)] =NP.theory of computation代写

(c)(1 point) Show that there exists a language L which is in NP but which is notNP-hard. theory of computation代写 