Introduction to the Theory of Computation

Homework #8

Posted by James on May 28, 2011

Due: Friday, June 3rd, in class.

Reading assignment: Sipser, Section 10.2.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

Each problem is worth 20 points unless otherwise noted.

NP, RP, and BPP

We have already learned about the class BPP. The complexity class RP is the set of languages decidable by a polynomial-time probabilistic Turing machine M, where M always rejects inputs NOT in the language, and accepts inputs in the language with probability at least 1/2. (Recall that BPP is the similar, but is required to accept yes inputs with probability at least 2/3 and reject no inputs with probability at least 2/3.)

Show that $\mathrm{RP} \subseteq \mathrm{NP}$ . Then show that if $\mathrm{NP} \subseteq \mathrm{BPP}$ , then $\mathrm{NP} = \mathrm{RP}$ .

ZPP

A ZPP-machine is a probabilistic Turing machine that always runs in polynomial time, but is allowed to sometimes output “DON’T KNOW.” To decide a language, such a machine must always be correct when it accepts or rejects, and on any input it can only say “DON’T KNOW” at most half the time. ZPP is the class of languages decided by ZPP-machines.

Show that $\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}$ , where $\mathrm{RP}$ is defined in the first problem, and $\mathrm{coRP}$ is the class of languages $\overline{L}$ where $L \in \mathrm{RP}$ .
BPL

Let BPL be the collection of languages that are decided by probabilistic log-space Turing machines with error probability 1/3 (so this is the same as BPP, but now we require the machine to run in logarithmic space). Prove that $\mathrm{BPL} \subseteq \mathrm{P}$ .

Posted in Homework, Reading | Leave a Comment »

Friday’s class: P/poly and Adleman’s Theorem

Posted by James on May 28, 2011

We introduced the class of languages decidable by polynomial-size circuit families, and proved that $\mathrm{BPP} \subseteq \mathrm{P}/\mathrm{poly}$ .

Posted in Lecture | Leave a Comment »

Wednesday’s class: Read-once branching programs

Posted by James on May 27, 2011

We used the Schwartz-Zippel Lemma to prove that the equality problem for read-once branching programs is in BPP. The latter result and proof are in Section 10.2 of Sipser.

Posted in Lecture | Leave a Comment »

Monady’s class: Probabilistic Turing machines

Posted by James on May 25, 2011

On Monday, we discussed the definition of BPP (bounded-error probabilistic polynomial time), and saw the proof of the Schwartz-Zippel Lemma (click on the link to see the proof).

Posted in Lecture | Leave a Comment »

Homework #7

Posted by James on May 19, 2011

Due: Wednesday, May 25th, in class.

Reading assignment: Sipser, Chapter 8.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

Each problem is worth 20 points unless otherwise noted.

Bounded degree spanning trees

A spanning tree of an undirected graph G=(V,E) is a subset of the edges E’ such that the graph (V,E’) is a connected tree (i.e. is connected and has no cycles.)

For any number k, define the language DEGREE-k-SPANNING-TREE to be

$\displaystyle \{ \langle G \rangle : G \textrm{ has a spanning tree of max. degree at most } k\}$
1. Show that DEGREE-2-SPANNING-TREE is NP-complete.
2. Use a reduction from DEGREE-2-SPANNING-TREE to show that DEGREE-3-SPANNING TREE is NP-complete.
3. Generalize this to show that DEGREE-k-SPANNING-TREE is NP-complete for every k.
Word ladders
A ladder is a sequence of strings $s_1, s_2, \ldots, s_k$ where every string differs from the preceding one in exactly one character. For example, the following is a ladder of English words: dork, pork, park, lark, lard, lord, cord, core, bore.

Consider the language $\textrm{LADDER}_{\textrm{DFA}}$ defined as the set of all triples $\langle M,s,t \rangle$ such that M is a DFA and L(M) contains a ladder of strings starting with s and ending with t. Show that $\textrm{LADDER}_{\textrm{DFA}}$ is in PSPACE.
Balanced parentheses
Let A be the language of balanced parentheses. For example, (()) and (()(()))() are in A, but )( is not. Show that A is in $L$ (log-space).
Extra credit: Undirected cycles
Show that the language of undirected graphs G such that G contains a cycle is in $L$ .

Posted in Homework, Reading | Leave a Comment »

Homework #6

Posted by James on May 11, 2011

Due: Wednesday, May 18th, in class.

Reading assignment: Sipser, Chapter 7.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

Each problem is worth 20 points unless otherwise noted.

Half cliques

Let HALF-CLIQUE be the language

$\displaystyle \{ \langle G \rangle : G \textrm{ is an undirected graph that has a clique of size at least } n/2 \},$

where n is the number of vertices in G. Prove that CLIQUE $\leq_p$ HALF-CLIQUE.

Dominating sets

First, read the proof of Theorem 7.44 in Sipser to learn that the VERTEX-COVER problem is NP-complete. Now use a reduction from VERTEX-COVER to prove that the following problem is NP-complete:

$\displaystyle \textrm{DOMINATING-SET} = \{ \langle G,k\rangle : G \textrm{ has a dominating set with } k \textrm{ nodes}\}.$

A subset of a graph G is a dominating set if every other node of G is adjacent to some node in the subset.

Arithmetization

Say that a multi-variate polynomial $p$ has a binary root if there is an assignment $(x_1, x_2, \ldots, x_n) \in \{0,1\}^n$ such that $p(x_1, x_2, \ldots, x_n)=0$ . Now define the language BINARY-ROOT as

$\displaystyle \{ \langle p \rangle : p \textrm{ is a polynomial in } n \textrm{ variables with integer coefficients and } p \textrm{ has a binary root}\}.$

First, show that BINARY-ROOT is in NP.

Now, show that the problem is NP-complete by proving that 3SAT $\leq_p$ BINARY-ROOT.

[Hint: First, figure out how to convert each clause into a polynomial that evaluates to 0 if and only if the clause is satisfied. Then create a polynomial q that evaluates to 0 if and only if all inputs are 0. Finally, use q and the individual polynomial for each clause to complete the reduction.]

Posted in Homework, Reading | 2 Comments »

Ladner’s theorem and NP-intermediate problems

Posted by James on May 10, 2011

http://en.wikipedia.org/wiki/NP-intermediate

Posted in Reading | Leave a Comment »

Homework #5

Posted by James on May 7, 2011

Due: Friday, May 13th, in class.

Reading assignment: Sipser, Chapter 7.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

Each problem is worth 20 points unless otherwise noted.

NP operations

Show that if A and B are in NP, then so are $A \cup B$ and $A \cap B$ .
Self-reducibility
Show that if P=NP, then a polynomial time algorithm exists which, given a 3SAT instance $\phi$ , actually produces a satisfying assignment if $\phi$ is satisfiable.
Concatenation in P
Show that if a language L is in $\mathcal P$ , then so is the language

$\displaystyle L^* = \{ x_1 x_2 \cdots x_k : k \geq 0, \forall i, x_i \in L \}$

Hint: You should use dynamic programming. If you don’t know what it is, read about it.

Posted in Homework, Reading | Leave a Comment »

Midterm on Wed

Posted by James on April 30, 2011

The midterm is coming up next week on Wednesday.

It will be in class, 50 minutes, and everyone is allowed to bring in one page of notes. The style of the questions will be very similar to the homework, and the exam will cover only Chapters 3-6.2 of Sipser, and as I said in class, you only need to understand the ideas in Section 6.2, not the specifics. There will be no questions on time complexity.

Besides understanding the basic notions (especially reductions!), you should be comfortable with things like Problem 1 of HW#3 and Problem 2 of HW#4. Be prepared to give explanations of why certain problems are decidable and others are undecidable.

Post comments if you have any questions!

Posted in Announcement, Reading | Leave a Comment »

Homework #4

Posted by James on April 21, 2011

Due: Wednesday, April 27th, in class.

Reading assignment: Sipser, Chapters 5 and 6.1-6.2.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.

Problems

Each problem is worth 20 points unless otherwise noted.

Search vs. decision
Let $f : \Sigma_0^* \to \Sigma_0^*$ be an arbitrary computable function over strings in $\Sigma_0$ . Define a related language $L_f \subseteq \Sigma^*$ and describe a Turing machine to compute $f$ using a machine that decides $L_f$ . Also show how to decide $L_f$ using a machine that computes $f$ . The alphabet $\Sigma$ does not have to be the same as $\Sigma_0$ .

Living like it’s 2011.

Tell where the following languages are (a) decidable, (b) recognizable by not decidable, (c) co-recognizable but not decidable, or (d) neither recognizable nor co-recognizable. Justify your answer.
1. $\{ \langle M \rangle : \textrm{TM } M \textrm{ halts within 2011 steps on some input} \}$
2. $\{ \langle M \rangle : \textrm{TM } M \textrm{ halts within 2011 steps on every input} \}$

Formatting doesn’t help.

Suppse that $A \subseteq \{ \langle M \rangle : M \textrm{ is a decider} \}$ and that $A$ is Turing-recognizable. Prove that there is a decidable language $D$ such that $L(M) \neq D$ for any $M$ with $\langle M \rangle \in A$ . (This means we can’t come up with some restricted easy-to-recognize format for deciders that captures all decidable languages.)