6.045: Automata, Computability and Complexity 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 (6 points) 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.
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 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}.theory of computation代写
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 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 (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.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 (3 points) 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 (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 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 Lj∈ TIME[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.
其他代写：function代写 web代写 编程代写 数学代写 algorithm代写 python代写 java代写 project代写 dataset代写 analysis代写 C++代写 金融经济统计代写 essay代写 assembly代写 program代写 code代写 CS代写
