### CS4123 Theory of Computation. B2002 Solutions - EXAM 2 December 12, 2002.

#### Instructions

• Ask in case of doubt

### Problem 1 - Decidability (25 points)

Let Sigma be an alphabet. Show that the following language is decidable by constructing a Turing machine that decides it:
ALLDFA = {<D> | D is a DFA and L(D) = Sigma*}
In other words, construct a Turing machine that decides the following problem:
• Given: The codification of a deterministic finite automaton D
• Output:
• Accept, if D accepts each and every word in Sigma*, i.e. L(D) = Sigma*.
• Reject, otherwise.

Solution 1.

Let's construct a Turing machine M to decide the ALLDFA problem.

M =" On input x,

1. 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.
2. Construct the following DFA AC: AC = (Q,Sigma,delta,q_0,Q-F).
3. Run <AC> on the Turing machine T that decides the EDFA problem (see Theorem 4.4).
4. If T accepts <AC>, then accept x.
5. If T rejects <AC>, then reject x."
It is easy to see that L(A) and L(AC) are the complement of each other with respect to Sigma*. That is, L(A) = Sigma* - L(AC).
Hence, L(A) = Sigma* iff L(AC) = empty. Determining if L(AC) 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 ALLDFA problem.

M =" On input x,

1. 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.
2. Construct the DFA S = ({q},Sigma,delta,q,{q}), where delta(q,a) = q, for all a in Sigma.
3. Run the pair <A,S> on the Turing machine F that decides the EQDFA problem (see Theorem 4.5).
4. If F accepts <A,S>, then accept x.
5. If F rejects <A,S>, then reject 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.

### Problem 2 - Semi-Decidability (25 points)

Show that the acceptance problem for Turing machines
ATM = {<M,w> | M is a TM and M accepts input w} is semi-decidable.

In other words, construct a Turing machine that semi-decides the following problem:

• Given: The codification of a Turing machine M and a word w
• Output:
• Accept, if the machine M accepts input w.
• Reject, otherwise.
Solution
Let's construct a semi-decider U for ATM:

U = "On input x,

1. Check that x codifies a Turing machine M and a string w. If not, reject x.
2. Run the machine M on input w.
1. If M accepts w, then accept x = < M,w >.
2. If M rejects w, then reject x = < M,w >.
3. [note that if M loops on w, then U will loop on x.]"
U semi-decides ATM, because U accepts < M,w > if and only if M accepts w.

### Problem 3 - Undecidability (25 points)

Show that the equivalence problem for Turing machines
EQTM = {<M1,M2> | M1 and M2 are TMs and L(M1) = L(M2)} is undecidable.

In other words, show that there is NO Turing machine that decides the following problem:

• Given: The codifications of two Turing machines M1 and M2
• Output:
• Accept, if L(M1) = L(M2).
• Reject, otherwise.
Solution
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.

### Problem 4 - NP-Completeness (25 points)

Consider the Traveling Salesman problem:

• Given: A graph G=(V,E); a positive cost c(e) for each edge e in E; and a positive integer B.
• Output:
• "Yes", if there is a simple tour of all the vertices in G (that is 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.
The cost of a tour is the sum of the costs of all the edges in the tour.
• "No", otherwise.

1. (10 points) Show that the TRAVELING SALESMAN problem is in the class NP.

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 v1,...,vn
be the resulting list of nodes (in that order!).
O(n3)  2. For each two consecutive nodes vi and vi+1
on that list (including the 1st and the last nodes, i.e. v1, vn)
check that there is an edge in E connecting vi and vi+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(n3) time in the worst case, since there are n edges that we need to check for existence, and it'll take O(n2) to look for each of them in E (since E contains at most n2 edges). The time complexity of this nonderministic Turing machine is O(n) + O(n3) + O(n) + O(1) = O(n3). Since this is polynomial in n, this problem is in NP.
2. (15 points) Show that the TRAVELING SALESMAN problem is NP-complete.

Hint: Show that HAMILTONIAN CIRCUIT <=p TRAVELING SALESMAN
where HAMILTONIAN CIRCUIT is the following NP-complete problem:

• Given: A graph G=(V,E).
• Output:"Yes", if there is a simple tour of all the vertices in G (that is a loop that visits each and every one of the vertices in the graph exactly once). "No", otherwise.
Solution
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:

• copying G into G' takes O(n2) time as we need to copy O(n) nodes and at most O(n2) edges.
• setting the costs c(e)'s takes O(1) for each one and since there are at most O(n2) edges, the whole process takes O(n2) time.
• setting B to n takes O(1), although counting the nodes in V (to determine n) takes O(n).
Hence the whole translation takes: O(n2) + O(n2) + O(n) = O(n2).

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.

### Problem 5 - Extra Credit (20 points)

The following two extra credit problems are unrelated to each other.
1. (10 points) Show that if the HAMILTONIAN CIRCUIT problem can be solved with a deterministic Turing machine in polynomial time in the size of its input, then P = NP. Explain your answer.

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 CIRCUIT

Now, 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 MC to decide C as follows:

MC = "On input w,

1. Compute f(w)
2. Run f(w) on H, and output whatever H outputs."

Note that MC 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.

2. (10 points) Let A and B be two languages. We say that A is mapping reducible to B (denoted by A <=m B) whenever there is 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.

Show that if A <=m B and B is semi-decidable, then A is semi-decidable.

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 SB 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 SB and f, let's construct a TM SA that semi-decides A:

SA = "On input w,

1. Compute f(w)
2. Run f(w) on SB, and output whatever SB outputs."

Note that

```
w belongs to A
iff f(w) belongs to B
iff SB accepts f(w)
iff SA accepts w.
```
Hence, SA is a semi-decider for A.