CS 154 Introduction to Automata and Complexity Theory Handout 22

Winter 1996  R. van Glabbeek  March 18

Solution Set 8

1. (Graded by Stan Birchfield)

Let P and Q be two DTM programs. If their transfer functions φ_{P} and φ_{Q} are identical, then P and Q accept the same language. Let’s call this language L. Now if L is self-aware, then P and Q are both self-aware, and if L is not self-aware, then neither P nor Q is self-aware. Let χ_{SL}(P) denote whether the program P is in the set SL. Then

φ_{P} = φ_{Q} ⇒ χ_{SL}(P) = χ_{SL}(Q).

Therefore, SL is an index set by definition.

We will now show that SL is nontrivial by first showing that it contains at least one DTM program and then by showing that it does not contain all DTM programs. We may assume that there exist self-aware DTRs, by the Fixed-Point Theorem. Let P_{sa} be such a DTR. Then P_{sa} recognizes {⟨P_{sa}⟩}, which is hence a self-aware language. By changing reject states to nonterminating states, we can easily construct a DTA which accepts {⟨P_{sa}⟩}. Since this DTA accepts a self-aware language, it is a self-aware DTA and is therefore contained in the set SL. Therefore, SL is not empty.

Now consider the inattentive DTA which never halts. It clearly does not accept a self-aware language, because it does not accept any language. Therefore, it is not contained in the set SL. Since SL is neither empty nor consists of all DTM programs, then SL is nontrivial.

By Rice’s Theorem, any nontrivial index set is undecidable. Therefore, SL is undecidable and hence is not recursive.

2. Let DOUBLESAT be the problem of determining whether a CNF formula has at least two satisfying assignments, i.e.,

DOUBLESAT = {ϕ : ϕ has at least two satisfying assignments }.

Show that DOUBLESAT is NP-complete.

Solution: DOUBLESAT is in NP as two candidate truth value assignments for a given formula ϕ can be checked to be both different, and satisfying ϕ in polynomial time. We show that DOUBLESAT is NP-complete by reducing 3-SAT to DOUBLESAT. Given a formula ψ in 3-SAT, choose the polynomial transformation f(ψ) to be f(ψ) = ψ ∨ (x ∧ \overline{x}), where x is a variable not appearing in ψ. The function f is readily seen to satisfy polynomial computability, and the correctness requirement. Since 3-SAT is an NP-complete language (Theorem 9.15), we have shown than every NP problem is reducible to DOUBLESAT (we have that every NP problem is reducible to 3-SAT via NP-completeness of 3-SAT; upon composition with f, every NP problem can be reduced to an instance of DOUBLESAT).

3. (Graded by Ngai Ngai Lam and Xinyang Fan) See hardcopy for solution.

4. (Graded by Jian Bao) See hardcopy for solution.

Extra credit problems: Solutions will be provided on demand - talk to course staff about any problem of interest.