Complexity and Computability Homework and Reading Assignments

• Wednesday, November 28.
  • Read the syllabus in detail.
  • Finish question 9 from the questions distributed last class.
  • Skim Chapter 3.

• Monday, December 3
  • Read: the "decidable problems concerning regular languages" section from Chapter 4 and notes from last class.
  • Show that the problems X_DFA and Y_DFA are decidable.
  • If you don't remember much about CFG's, skim Section 2.1.
  • Look at the answer to Problem 4.10 [4.9 in second edition] to see a different algorithm for INFINITE_DFA.
  • Skim the first part of Section 4.2 (pp 201-206 [173-178]).
  • Look over Homework 1.

• Wednesday, December 5
  • Homework 1, due 12/5, 4:00pm:
    • Before you start on the homework, please read the rules on collaboration and submission in the syllabus.
    • Also keep in mind that, as stated in the syllabus, I will not answer homework questions the day that the homework is due.
    • And keep in mind that not only should your answers be correct, your write-up should also convince me that your answers are correct!
    And now.... the actual assignment:
    1. Look at the Venn diagram that shows the relationships (assuming P not equal NP) between the language classes from question 1 from the questions distributed 11/26. For each area in your Venn diagram, give a simple example of a language that lives there. So,
       1. Give a simple example of a finite language.
       2. Give a simple example of language that is regular, but not finite.
       3. Give a simple example of language that is a CFL, but not regular.
       4. Give a simple example of language that is in P, but not a CFL.
       5. Give a simple example of language that is NP-complete.
       6. Give a simple example of a language that is in NP, probably not NP-complete, and probably not in P.
       7. Give a simple example of language that is decidable, but not in NP.
       8. Give a simple example of language that is RE, but not decidable.
       9. Give a simple example of language that is not RE.
       You may look this up (most answers can be found in the book), but try to understand your answers. If it is not completely obvious that your answer is correct, please add a brief explanation.
    2. Look at the language classes from question 1 from the questions distributed 11/26. Draw one Venn diagram with these classes (call them NP, P, RE, CFL, DECIDABLE, FINITE, NPC, REGULAR) and the corresponding co-classes: coNP, coP, coRE, coCFL, coDECIDABLE, coFINITE, coNPC, and coREGULAR. For C a class of languages, coC is the class of all languages that are the complement of a language in C. See page 209 (181) for co-Turing-recognizable (coRE). Assume that NP is not equal to coNP. You may look up the relationship between the classes, but try to understand why these relationships hold.
       Note: You may assume that the alphabet is not empty, and so every co-finite language is infinite (but not vice versa!).
    3. Consider the problem of determining whether the language accepted by a DFA is non-trivial, i.e., given a DFA, accept if and only if the language recognized by the DFA is not the empty set and not Sigma*. Formulate this problem as a language and show that it is decidable. Give a high-level description, using Sipser notation, of a TM that decides your language, and briefly explain why your TM decides the language.
    4. Define SIZEONE_DFA as follows: SIZEONE_DFA = { < A > | A is a DFA and L(A) contains exactly one string }. Show that SIZEONE_DFA is decidable. Give a high-level description, using Sipser notation, of a TM that decides your language, and briefly explain why your TM decides the language.
    5. Come up with an interesting decision problem concerning regular languages (you don't have to show whether it's decidable). Briefly explain why your problem is interesting.

• Monday, December 10
  • Read: Chapter 4, first 5 pages of Chapter 5, notes from last class as far as covered.
  • Show that EQ_CFG is undecidable. Use Theorem 5.13 (ALL_CFG is undecidable). Write your proof as a proof by contradiction, like the proofs in Section 5.1.
  • Look at the language E_TM (see Theorem 5.2). Is E_TM RE, coRE, both, or neither? Explain your answer.
  • Look over Homework 2.

• Wednesday, December 12
  • Homework 2, due 12/12, 4:00pm:
    1. Let PAL_DFA be defined as follows. PAL_DFA = { < M > | M is a DFA that accepts some palindrome }. Show that PAL_DFA is decidable: Give a high-level description, using Sipser notation, of a TM that decides your language, and briefly explain why your TM decides the language.
    2. Show that (in contrast to the case for DFAs) that it is NOT the case that for all PDAs M, L(M) is infinite if and only if there is a state q in M such that (q is reachable from the start state, there is a cycle from q to q, and there is an accepting state that is reachable from q). Give an explicit counterexample (give a state diagram using Sipser's PDA definition and notation) and explain why your example is a counterexample.
    3. Does your answer to the previous question imply that the finiteness problem for PDAs is undecidable? Does your answer to the previous question imply that the finiteness problem for PDAs is decidable? Briefly explain your answers.
    4. Define SIZEONE_CFG as follows: SIZEONE_CFG = { < G > | G is a CFG and L(G) contains exactly one string }. Show that SIZEONE_CFG is decidable: Give a high-level description, using Sipser notation, of a TM that decides your language, and briefly explain why your TM decides the language.
    5. Theorem 5.1 states that HALT_TM is undecidable. In the book, this is shown by reducing A_TM to HALT_TM. In this question, you should give a direct proof (by diagonalization) that HALT_TM is undecidable.
    6. Consider the problem of determining whether the language accepted by a context-free grammar is non-trivial, i.e., given a CFG, accept if and only if the language generated by the CFG is not the empty set and not Sigma*.
       1. Formulate this problem as a language.
       2. Show that this language is undecidable. (You may use Theorem 5.13).
       3. Show that this language is Turing-recognizable (RE).
       4. Is this language co-Turing-recognizable (coRE)? Briefly explain your answer.

• Monday, December 17
  • Read 5.1 and 5.2 and related notes.
  • Think about the reduction from PCP to CFG ambiguity (last slide of notes).
  • Look over Homework 3.

• Wednesday, December 19
  • Read 5.3 and related notes.
  • Homework 3, due 12/19, 4:00pm:
    1. Let B be the following language B = { < M > | M is a TM and M on input 1011 does not halt}.
       1. Explain why the undecidability of B does not follow directly from Rice's Theorem.
       2. Problem 5.30 (b). (You may want to look at the answer to Problem 5.30 (a) first.)
       3. Show that B is undecidable.
    2. In the proof of the undecidability of PCP (Section 5.2), it is shown how to convert a TM M and input w into an instance P' of PCP such that M accepts w iff P' has a match that starts with the first domino. (This is the construction from pages 228-232 [200-204].) To get a feeling for this construction, we will look at an example. Let M = M₂ from page 172 [144], and let w = 00.
       1. Give the sequence of configurations that M₂ enters on input 00.
       2. In this example, what is the first domino of P'? (See part 1 on page 229 [201].)
       3. In this example, how many dominos are there in P'? Briefly explain your answer.
       4. In this example, give a match of P' (as a sequence of dominos) that starts with the first domino. (This match will correspond to the sequence of configurations of M₂ on input 00.)
    3. A RIGHTTM is a Turing machine that can only move right. The formal (7-tuple) definition of a RIGHTTM is like the definition of a TM, except that delta is a function from Q x Gamma to Q x Gamma x {R}.
       In this question, you will show that the acceptance problem for RIGHTTMs (A_RIGHTTM) is decidable.
       1. Give the definition of A_RIGHTTM in set notation.
       2. Give a high-level description, using Sipser notation, of a decider for A_RIGHTTM.
       3. Explain in a couple of lines why your TM from part (2) is a decider, and why it decides A_RIGHTTM.
       4. Consider the class of languages that can be accepted by a RIGHTTM. How does this class relate to the other classes of languages that you have seen? Explain your reasoning.
    4. Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell.
       1. Formulate this problem as a language.
       2. Show that this language is undecidable.
    5. Define SIZEONE_LBA as follows: SIZEONE_LBA = { < M > | M is a LBA and L(M) contains exactly one string }. Is SIZEONE_LBA decidable? RE? coRE? Informally explain your reasoning.

• Monday, January 7
  • Skim 7.1 and 7.2.
  • Look over Homework 4.

• Wednesday, January 9
  • Read: TBA
  • Homework 4, due 1/9, 4:00pm:
    1. This question is about that SIZEONE_LBA from the previous homework. We discussed this the last class before break.
       1. Prove that SIZEONE_LBA is not RE.
       2. Prove that SIZEONE_LBA is not coRE.
    2. Prove that the class of languages that can be recognized by a RIGHTTM (see previous homework) is exactly the class of regular languages.
    3. This question is about problem ALWAYSHALT_TM from slide 5 of the Chapter 5.1 notes.
       1. Explain formally why the undecidability of ALWAYSHALT_TM does not follow directly from Rice's theorem. (Use the "in more formal terms" formulation of Rice's theorem from Problem 5.28.)
       2. Define function f as follows. For M a TM and w a string, f(< M,w> ) = < M >. Explain why f is not a many-one reduction from HALT_TM to ALWAYSHALT_TM.
       3. Show that ALWAYSHALT_TM is not in coRE.
       4. Show that ALWAYSHALT_TM is not in RE.
    4. Exercise 7.4.

• Monday, January 14
  • Read: 7.3.
  • Go over the algorithms from Chapter 4 (book and notes). Which of the algorithms are polynomial-time algorithms?
  • Answers to RIGHTTM questions.

• Wednesday, January 16
  Midterm!

• Monday, January 21
  • Read: 7.3, notes from last class.
  • Skim 7.4.
  • Show that VERTEX COVER, INDEPENDENT SET, and CLIQUE all polynomial-time many-one reduce to each other.
  • Look over Homework 5.

• Wednesday, January 23
  • Read: 7.4, skim 7.5.
  • Homework 5, due 1/23, 4:00pm:
    1. A Boolean formula is a tautology if it is satisfied by every assignment. Give a polynomial-time algorithm to decide whether a Boolean formula in CNF is a tautology. Briefly explain your algorithm and explain why it is a polynomial-time algorithm.
    2. Exercise 7.12 [7.11] Show this in two different ways, as in the proofs of Theorems 7.24 and 7.25:
       1. Give a polynomial-time verifier for ISO, and
       2. Give a polynomial-time NTM that decides ISO.
    3. Look at the following list of decision problems about vertex covers (see page 312 [284]): (Note: we will go over a similar question in Monday's class)
       1. Given an undirected graph G and an integer k, does G have a vertex cover of size >= k?
       2. Given an undirected graph G and an integer k, does G have a vertex cover of size <= k?
       3. Given an undirected graph G and an integer k, does G have a vertex cover of size k?
       4. Given an undirected graph G, does G have vertex cover of size 100?
       5. Given an undirected graph G and an integer k, does G have a smallest vertex cover of size k?
       6. Given an undirected graph G and an integer k, does G have a largest vertex cover of size k?
       7. Given an undirected graph G and an integer k, does G have a smallest vertex cover of size < k?
       8. Given an undirected graph G and an integer k, does G have a smallest vertex cover of size > k?
       Answer the following questions. You do not have to explain your answers. (Assume that P is not equal to NP, and that NP is not equal to coNP).
       1. List all the problems from the list that are in P.
       2. List all the problems from the list that are in NP.
       3. List all problems from the list that are NP-complete.
       4. List all the problems from the list that are in coNP.
    4. Problem 7.22 [7.21].
    5. Read the proof of Theorem 7.55. You might think that the u^mid nodes are not necessary. So, look at the following simplification: Replace each node u of G except for s and t by a pair of nodes uⁱⁿ and u^out, connect uⁱⁿ with u^out, and for the rest use the construction from the book. Show that this simplification doesn't work, i.e., that it is not a reduction from DHAMPATH to UHAMPATH. You should give an explicit counterexample and briefly explain your counterexample.

• Monday, January 28
  • Try: Problem 7.23 [7.22], Problem 7.40 [7.38]. After trying, look at the answers.
  • Look over Homework 6 in detail. This requires working your way through the proofs of Theorem 7.37 and 7.56.

• Wednesday, January 30
  • No class today. See email.
  • Homework 6, due 1/30, 4:00pm. Do five of the following six questions.
    1. Consider the problem PARTITION: Given a collection (multi-set) A of natural numbers, can A be partitioned into two subcollections that have the same sum? That is, does there exist a subcollection B of A such that Σ B = Σ (A - B)?
       Show that PARTITION is NP-complete.
    2. Problem 7.30 [7.28].
    3. Problem 7.38 [7.36] (Problem 7.40 [7.38] is somewhat similar.)
    4. Problem 7.41 [7.39] (Show that Claim 7.41 does not hold if we look at 2x2 windows. Give a simple concrete counterexample and explain your counterexample.)
    5. Recall that Sipser's definition of SUBSET-SUM is defined for multi-sets instead of sets. Let SSUBSET-SUM be the subset sum problem defined for sets, i.e., SSUBSET-SUM = { < S, t > | S is a set of natural numbers, t is a natural number, and for some subset S' of S, Σ S' = t }. SSUBSET-SUM is also NP-complete. To show NP-hardness, we will modify the proof of Theorem 7.56 to give a reduction from 3SAT to SSUBSET-SUM.
       1. Briefly explain why SSUBSET-SUM is in NP.
       2. Look at the reduction from the proof of Theorem 7.56. Explain how it can happen that there are duplicates among y1, z1, y2, z2, ...., yl, zl. Now explain how you can slightly modify the reduction so that this does not happen.
       3. More problematic is the fact that gi = hi. Modify the reduction so that there are no duplicates. You only need to change the reduction a bit. In particular, you should not further change y1, z1, y2, z2, ...., yl, zl, and keep the basic structure of g1, h1, ...., gk, hk, and t.
    6. Find an interesting NP-complete problem in your area of interest or cluster. In your own words, describe the problem, explain why it is an interesting problem, explain why the problem is in NP, give a citation to the paper that proved that this problem is NP-complete, and state which NP-complete problem was reduced to your problem. You should also try to understand the main idea of the reduction, but you don't have to report on that.

• Monday, February 4
  • Read through Chapter 8. (You don't have to be able to follow the details at this point.)

• Wednesday, February 6
  • Homework 7, due 2/6, 4:00pm.
    1. Student S proposes the following algorithm to compute a clique C of maximum size in a graph G.
       • Initialize C to the empty set.
       • Repeat the following 3 steps until G is empty.
       • Choose a vertex v of highest degree in the graph and add v to C.
       • Remove (from G) every vertex w != v that is not adjacent to v and remove all edges incident with w.
       • Remove v and all edges incident with v from G.
       1. Briefly explain why student S's algorithm always computes a clique C of G.
       2. Explain in a couple of lines why student S would become rich and incredibly famous if this algorithm would always compute a clique of maximum size.
       3. Crush student S's dreams of fame and fortune, by showing that this algorithm does not always compute a clique of maximum size.
    2. Let UNARY-SUBSET-SUM be the subset sum problem in which all numbers are represented in unary. (You may assume that all numbers involved are natural numbers.)
       1. Why does the proof of Theorem 7.56 fail to show that UNARY-SUBSET-SUM is NP-complete?
       2. Show that UNARY-SUBSET-SUM is in P. Hint: Use dynamic programming. Make sure you explain your algorithm and why it is in P.
    3. Show that if NP is not equal to coNP then PSPACE is not equal to the union of NP and coNP. Big hint: Prove this by contradiction and think about where TQBF goes. All you need to know about TQBF is that it is PSPACE-complete.
    4. Show that EQ_NFA (equivalence between NFAs) is in PSPACE. (Two NFAs are equivalent if they accept the same language.) You may want to have a look at Example 8.4 first.

  • Wednesday, February 13
    • Homework 8, due 2/13, 4:00pm. Do four of the following six questions. (If you do more than four questions, your best four questions will count.)
      1. Problem 8.18.
      2. Show that { < G, s, t, k > | G is a directed graph, s and t are vertices in G, and the length of a shortest path from s to t is k} is NL-complete.
      3. Look at Sipser's proof of Theorem 8.27 (NL = coNL). In class, we decided that we could probably modify Sipser's algorithm to avoid the second loop (the one starting at line 13). Do so. Try to follow Sipser's notation as much as possible and add comments so that I can understand your algorithm.
      4. EQ_NFA (from the previous homework) is PSPACE-complete. Find out whose result this is, and give the journal reference.
      5. A language A is self-reducible if there is a polynomial-time oracle Turing machine M (see Definition 9.17) such that A = M^A and such that M on inputs of length n queries only strings of length < n.
         1. Show that QBF is self-reducible.
         2. Show that every self-reducible language is in PSPACE.
      6. P^NP[log] is a subset of P^NP. It consists of all languages in P^NP such that the P-machine queries its NP oracle O(log n) times. P_tt^NP is also a subset of P^NP. It consists of all languages in P^NP such that the P-machine can query one list of strings to its NP oracle. The oracle will give back a list of answers. ODDSAT is the following problem: Given a list of Boolean formulas, is the number of satisfiable formulas in the list odd?
         1. Show that ODDSAT is in P_tt^NP.
         2. Show that ODDSAT is in P^NP[log].
         3. In fact, P^NP[log] = P_tt^NP. One of the inclusions is easy to show. State the easy inclusion and show it.
         4. For extra credit, show the converse inclusion.

  Complexity and Computability