CS 154 Introduction to Automata and Complexity Theory Handout 20

Winter 1996  R. van Glabbeek  March 6, 1996

Problem Set 8 Date Due: March 13, 1996

Reading: Floyd and Beigel, Chapter 0-9.7

Homework: Do the following exercises (FB refers to Floyd and Beigel The Language of Machines). Each problem must be submitted on a separate sheet. The homeworks must be solved without any collaboration. You are, naturally, more that welcome to discuss anything other than than solutions to the homeworks with others. In response to student requests, we will accept solutions to extra credit problems (only) at any time prior to their solutions being handed out.

1. (5 points) A DTR P is self-aware if it recognizes the language {⟨P ⟩}, where ⟨P ⟩ is the string encoding of P. You may assume that there exist self-aware DTRs (Section 8.2, if you are curious). A language L is self-aware if it is recognized by a self-aware DTR. Use Rice’s theorem to show that the set SL of DTAs that accept self-aware languages is not recursive. The more interesting part of this question can be found in the (optional) extra credit section.

2. (10 points) 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.

3. (15 points) 9.7-10 (FB page 651). Submit only answers for parts (c)-(f).

4. (15 points) Let MAXCLIQUE be the problem of determining whether k is the size of the largest clique in a graph G, i.e.,

MAXCLIQUE = {⟨G, k⟩ : the largest clique of G has k vertices}.

The notion of a clique is defined on page 640. It is not known whether MAXCLIQUE is in NP. Show, however, that if P = NP, then

(a) MAXCLIQUE ∈ P.

(b) There is a polynomial time algorithm which, given a graph G, finds one of its largest cliques.

(Over for extra credit and chapter summary)

Extra credit (optional)

1. Let DESCARTES be the set of self-aware DTRs (as described in problem 1). What does Rice’s theorem say about the set DESCARTES? Is DESCARTES recursive?

2. The Cat-and-Mouse Game is played by two players, “Cat” and “Mouse”, on an arbitrary undirected graph.The players take turns moving to a node adjacent to the one they are currently occupying. There is a special node of the graph called “Hole”. Cat wins if the two players ever occupy the same node. Mouse wins if he reaches the Hole before the preceding happens. The game is a draw if the two players ever simultaneously reach positions that they previously occupied. Let

HAPPYCAT = \{⟨G, c, m, h⟩ : \begin{matrix}G, c, m, h, are respectively a graph, and positions \\ of the Cat, Mouse, and Hole, such that the Cat \\ has a winning strategy \end{matrix} \}

Show that HAPPYCAT ∈ P. Chapter summary

Make sure you are familiar with the following concepts when having finished Chapter 9:

• The concepts P, NP and co-NP.

• Polynomial time reductions ≤_{m}^{p}.

• Reduction methods from search and optimization to decision.

• NP-completeness. What is a canonical NP-complete problem ?

• NP-completeness for symbol systems. Theorem 9.13 (FB page 630). Cook’s theorem (FB page 632).

• NP-complete problems, such as: Hamiltonian cycle, 3-SAT, Clique, 3-colorability.