Solution 1.
Let's construct a Turing machine M to decide the ALL_{DFA} problem.M =" On input x,
It is easy to see that L(A) and L(A^{C}) are the complement of each other with respect to Sigma*. That is, L(A) = Sigma* - L(A^{C}).
- Check that x codifies a DFA. If so, denote the DFA by A = (Q,Sigma,delta,q_0,F). If x doesn't codify a DFA, reject x.
- Construct the following DFA A^{C}: A^{C} = (Q,Sigma,delta,q_0,Q-F).
- Run <A^{C}> on the Turing machine T that decides the E_{DFA} problem (see Theorem 4.4).
- If T accepts <A^{C}>, then accept x.
- If T rejects <A^{C}>, then reject x."
Hence, L(A) = Sigma* iff L(A^{C}) = empty. Determining if L(A^{C}) is empty is decidable due to Theorem 4.5, and so determining if L(A) = Sigma* is decidable as well.
Alternative Solution 2.
Let's construct a Turing machine M to decide the ALL_{DFA} problem.M =" On input x,
Clearly S accepts every word in Sigma* and so L(S) = Sigma*. Given a DFA A, A belongs to ALLdfa iff L(A) = L(S). By Theorem 4.5 (EQUIVdfa is decidable), the condition L(A)=L(S) is decidable, and so determining if A belongs to ALLdfa is decidable too.
- Check that x codifies a DFA. If so, denote the DFA by A = (Q,Sigma,delta,q_0,F). If x doesn't codify a DFA, reject x.
- Construct the DFA S = ({q},Sigma,delta,q,{q}), where delta(q,a) = q, for all a in Sigma.
- Run the pair <A,S> on the Turing machine F that decides the EQ_{DFA} problem (see Theorem 4.5).
- If F accepts <A,S>, then accept x.
- If F rejects <A,S>, then reject x."
In other words, construct a Turing machine that semi-decides the following problem:
Let's construct a semi-decider U for A_{TM}:U = "On input x,
U semi-decides A_{TM}, because U accepts < M,w > if and only if M accepts w.
- Check that x codifies a Turing machine M and a string w. If not, reject x.
- Run the machine M on input w.
- If M accepts w, then accept x = < M,w >.
- If M rejects w, then reject x = < M,w >.
- [note that if M loops on w, then U will loop on x.]"
In other words, show that there is NO Turing machine that decides the following problem:
See the proof of Theorem 5.4 (page 176) in your textbook. [Of course your solution in the exam cannot be just stating that a theorem in the book proves this. You need to prove it yourself.
Solution
Let's construct a nondeterministic polynomial time Turing machine to show that this problem is in NP. Let n = |V|.NTS = "On input G=(V,E), a positive cost c(e) for each edge e in E; and a positive integer B do: O(n) 1. Nondeterministically, order the nodes in V. Let v_{1},...,v_{n} be the resulting list of nodes (in that order!). O(n^{3}) 2. For each two consecutive nodes v_{i} and v_{i+1} on that list (including the 1st and the last nodes, i.e. v_{1}, v_{n}) check that there is an edge in E connecting v_{i} and v_{i+1}. If at least one of those edges doesn't exist, reject the input. O(n) 3. Add up all the costs c(e) corresponding to those edges. o(1) 4. If they add up to a number less then or equal to B, accept the input. Otherwise reject the input.Note that step 2 takes O(n^{3}) time in the worst case, since there are n edges that we need to check for existence, and it'll take O(n^{2}) to look for each of them in E (since E contains at most n^{2} edges). The time complexity of this nonderministic Turing machine is O(n) + O(n^{3}) + O(n) + O(1) = O(n^{3}). Since this is polynomial in n, this problem is in NP.
Hint: Show that HAMILTONIAN CIRCUIT <=p TRAVELING SALESMAN
where HAMILTONIAN CIRCUIT is the following NP-complete problem:
Let's reduce HAMILTONIAN CIRCUIT to TRAVELING SALESMAN in polynomial time.
- Given an input to the HAMILTONIAN CIRCUIT problem
- A graph G=(V,E)
- Construct an input to the TRAVELING SALESMAN problem as follows:
- A graph G' = G=(V,E);
- a positive cost c(e)=1 for each edge e in E; and
- a positive integer B = n (the number of nodes in V).
Constructing this input to the TRAVELING SALESMAN problem from G=(V,E) is done in polynomial time in n = |V|. Here is why:
Hence the whole translation takes: O(n^{2}) + O(n^{2}) + O(n) = O(n^{2}).
- copying G into G' takes O(n^{2}) time as we need to copy O(n) nodes and at most O(n^{2}) edges.
- setting the costs c(e)'s takes O(1) for each one and since there are at most O(n^{2}) edges, the whole process takes O(n^{2}) time.
- setting B to n takes O(1), although counting the nodes in V (to determine n) takes O(n).
Now we need to prove that G belongs to HAMILTONIAN CIRCUIT iff the triple G,c(e),B belongs to TRAVELING SALESMAN. That is, we need to show that G contains a Hamiltonian circuit (that is a loop that visits each and every one of the vertices in the graph exactly once) if and only if G contains a loop that visits each and every one of the vertices in the graph exactly once having total cost less than or equal to B. But this is obvious, given the fact that we have set of cost of each edge to 1 and B = n.
Solution
See Theorem 7.28 in your textbook. Since HAMILTONIAN CIRCUIT is an NP-complete problem, then every problem C in the class NP is polynomial-time reducible to it (by the definition of NP-completeness). That is, there is a computable function f such that for all w in Sigma*, w belongs to C iff f(w) belongs to HAMILTONIAN CIRCUITNow, assume that there is a deterministic Turing machine H that decides the HAMILTONIAN CIRCUIT problem in polynomial time. Then one can construct a deterministic Turing machine M_{C} to decide C as follows:
M_{C} = "On input w,
- Compute f(w)
- Run f(w) on H, and output whatever H outputs."
Note that M_{C} runs in polynomial time in the size of w, since Step 1 runs in polynomial time (f is computable in polynomial time), and Step 2 runs in polynomial time as we're assuming H runs in polynomial time.
Given a deterministic polynomial time solution to HAMILTONIAN CIRCUIT, we have constructed a deterministic polynomial time solution to the NP problem C. Since this holds for all C in NP, then this would imply that P = NP.
Solution
See Theorem 5.22 in your textbook.Assume A <=_{m} B and B is semi-decidable. Since B is semi-decidable there exists a semi-decider S_{B} for B. Since A <=_{m} B then there exists a computable function f: Sigma* -> Sigma* such that for all words w in Sigma*, w belongs to A if and only if f(w) belongs to B.
Based on S_{B} and f, let's construct a TM S_{A} that semi-decides A:
S_{A} = "On input w,
- Compute f(w)
- Run f(w) on S_{B}, and output whatever S_{B} outputs."
Note that
w belongs to A iff f(w) belongs to B iff S_{B} accepts f(w) iff S_{A} accepts w.Hence, S_{A} is a semi-decider for A.