**CSC 8510:
Homework Assignments**

**Policy:**
Homework will not be graded, but the weekly quizzes will be mainly based on
your homework. Books or notes will not be allowed during the quiz. Using somebody's
help is OK doing homework, but not when writing the quiz.

A quiz will typically have two questions: one from the
latest homework assignment, and one from some earlier homework assignment.
Occasionally, however, questions may be asked that are not exactly on the list
of homework problems yet are similar or closely related to the latter; if you
have done homework with understanding (as opposed to memorization), answering
such questions should not be a problem.

**[January
19]**

**Material covered:** Slides 0.a-1.2.f

**Assignment:**

- Exercise 0.1 [Note: "
**N**" stands for natural numbers. See page 4.] - Exercise 0.2
- Exercise 0.3
- Exercise 0.4
- Exercise 0.5
- Exercise 0.6
- Exercise 1.1
- Exercise 1.2
- Exercise 1.3
- Exercise 1.6 (a,b,d,e,g,h,i,k,m,n)
- Exercise 1.7 (a,b,d,g)

**[January
26]**

**Material covered:** Slides 1.2.g-2.1.e

**Assignment:**

- Exercise 1.16 (a)
- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise 1.20 [Note:
stands for*S**a***È**]*b* - Exercise 2.3
- Exercise 2.4 (in this exercise,
means*w*^{R}read from right to left)*w* - Exercise 2.9 (ignore the question on ambiguity)

**[February
2]**

**Material covered:** Slides 2.1.f-3.1.k

**Assignment:**

- Exercise 3.1
- Exercise 3.5

·
Complete the following definitions: (1) A Turing machine ** M** is a

·
Design a fragment of a TM that, from a state “Beg?”, goes to a
state “Yes” or “No”, depending on whether you are at the beginning of the
tape or not, without corrupting the contents of the tape (Slide 3.1.i).

·
Design a fragment of a TM that, from a state “Go to the
beginning”, goes to the beginning of the tape and state “Done” (Slide 3.1.j).

·
Design a fragment of a TM that, beginning from the current cell,
shifts the contents of the tape to the right, typing in the current cell a 0
(Slide 3.1.k). Assume the tape alphabet is {0,1,-},
and that neither 0 nor 1 ever occurs after the leftmost blank on the tape.

·
Construct a Turing machine (provide a full diagram) for the
language **{#****·**^{n}**>****·**^{m }**| n>m} **(note: this is
similar to but NOT the same as the example on slide 3.1.f).

**[February
16]**

**Material covered:** Slides 3.1.l-3.3.c

**Assignment:**

- Theorem 3.13 with a brief description of its proof idea
(a few lines would suffice, showing your understanding of the essence of
the proof; do not go into technical details).

·
Theorem
3.16 with a brief description of its proof idea (a few lines would suffice,
showing your understanding of the essence of the proof; do not go into
technical details).

- The definitions of "
*M**computes*", "*g*is*g*" and "the*computable*of*graph*" (Slide 3.2.g).*g* - For a bit string
,*w***NOT(**means*w*)with all bits changed. For example,*w***NOT(****11010)=00101**. Construct a Turing machine with an output that computes function**NOT**. - Proof idea for the Theorem given on Slide 3.2.h.

**[February
23]**

**Material covered:** Slides 3.3.d-4.2.b.1

**Assignment:**

- What is the Church-Turing thesis all about? (do not
just write something like "algorithms = TM"; write a couple of
sentences showing that you understand what you are writing).
- Exercise 3.7.
- Exercise 4.1(a,b,c,e)
- Exercise 4.3.
- What language does the universal Turing machine
recognize and how does it work?
- Theorems (with proofs) 4.1, 4.2, 4.4, 4.11.

**[March
2]**

**Material covered:** Slides 4.2.c -5.3.d

**Assignment:**

- Prove
Theorem 4.23.
- Prove
that if a language
and its complement*L*are both recognizable, then__L__is decidable (Hint: the idea is, in fact, already given in the proof of Theorem 4.23. More explicitly, this is Theorem 4.22 of the textbook).*L* - Prove
that the halting problem is recognizable (Hint: similar to the theorem on
Slide 4.2.a).
- Prove that the halting problem is undecidable (Theorem
5.1).
- The
definitions of "
" and "*mapping reduction*" (Slide 5.3.a).*mapping reducible* - In each
case below, find (precisely define) a particular function that is a
mapping reduction of
to*A*. Both*B*and*A*are languages over the alphabet*B***{0,1}**.

is the language described by*A***1**,^{*}0^{*}*B***01**^{*}0^{*}*A***={***w***|**the length ofis even*w***}**,*B***={**the length of*w*|is odd*w***}***A***=**the length of*B*={*w*|is even*w***}***A***={****0,1}**,^{*}*B***={00,1,101}**

- Prove that if a
language
is mapping reducible to a language*A*and*B*is recognizable, then*B*is recognizable (hint: very similar to the proof of Theorem 5.22).*A* - Describe a function
which is a mapping reduction of the acceptance problem to the halting
problem (Slide 5.3.d).

**[March
16]**

**Material covered:** Slides 7.1.a – 7.1.n

**Assignment:**

- Definitions 7.1, 7.2,
7.5, 7.7.
- Exercise 7.1.
- The work of the
machines
**M1**,**M2**,**M3**(Slides 7.1.k, 7.1.l, 7.1.m) and an analysis of their time complexity. - How do the two
classes
**TIME(n)**and**TIME(2n)**compare (are they equal, or one (and which one) is a proper subset of the other, or neither)? Briefly justify your answer. - How do the two
classes
**TIME(n**and^{2})**TIME(2**compare (are they equal, or one (and which one) is a proper subset of the other, or neither)? Briefly justify your answer.^{n}) - Theorem (with proof
idea) 7.8.

**[March
23]**

**Material covered:** Slides 7.1.o – 7.3.i

**Assignment:**

- Exercises 7.3,
7.8, 7.9, 7.10
- Definitions
7.9, 7.12, 7.18, 7.19
- Theorems
(with proofs) 7.11, 7.14, 7.15, 7.20

**[March
30]**

**Material covered:** Slides 7.3.g – 7.4.i

**Assignment:**

- Exercises
7.12, 7.5.
- Definitions 7.21, 7.28, 7.29.
- Theorems
(with proofs) 7.24, 7.25, 7.32.

**[April
6]**

**Material covered:** Slides 7.3.j (again), 7.4.j, 7.4.k, 7.4.w, 7.5.a-7.5.k

**Assignment: **

- The definitions of coNP and EXPTIME (given on slide 7.3.j).
- The intuitive characterizations of P, NP, coNP and EXPTIME (given on
slide 7.3.j).
- What do we know and what do we not know about the
relationships (equal? subset?) between P, NP, coNP,
EXPTIME? (again, given on slide 7.3.j).
- Definition 7.34
- Theorems (with proofs) 7.35, 7.36.
- From the proof of Theorem 7.44, you should know and be
able to write in general terms (not merely examples) about: (1) how to
construct
**<G,k>**from**f**; (2) why it is the case that if**f**is satisfiable, then**G**has a vertex cover of size**k**; (3) why it is the case that if**G**has a vertex cover of size**k**, then**f**is satisfiable. - Remember the procedure given in the proof of Theorem 7.46 --- the procedure for converting a
3cnf-formula
**f**into a graph**G**such that**fÎ****3SAT**iff**G****Î****HAMPATH**. Apply it to the formula**f****= (xÚxÚz)****Ù****(**__x__Ú__z__Ú__z__)**Ù****(**__x__ÚzÚz)

**[April
20]**

**Material covered:** Slides 7.5.l-7.5.o,
8.0.a-8.1.a, 8.2.a, 8.3.a-8.3.b, 8.3.e-8.3.f

**Assignment: **

- Theorem (with proof) 7.46.
Since this proof is long, any part of it may be asked on the quiz, such as
(1) how to construct
**G**from**f**, (2) why it is the case that if**f**is satisfiable, then**G**has a Hamiltonian path, and (3) why it is the case that if**G**has a Hamiltonian path, then**f**is satisfiable. - Prove that UHAMPATH is
NP-complete (Theorem 7.55). You can assume the NP-completeness of HAMPATH is already known.
- Definitions 8.1, 8.2, 8.6, 8.8.
- Show that SAT can be decided in linear space (Example
8.3).
- What does Savitch's theorem
say? M(no proof required
- What do we know and do not know about the relations
(equal? subset?) between P, NP, PSPACE, NPSPACE, EXPTIME?

**[April
27]**

**Material covered:** Slides 8.3.d, 8.3.g-8.3.h, 8.4.a-8.4.d, 8.5.a-8.5.d, 8.6.d

**Assignment: **

· Show that TQBF
is in PSPACE (Slide 8.3.d)

- Exercises
8.3, 8.5
- Definitions
8.17, 8.22
- Theorem
(with proof) 8.23
- Show
that
**{0**^{k}1^{k}| k**³0}****Î**L (Example 8.18). - Show
that PATH
**Î**NL (Example 8.19).

· What do we know and do not
know about the relations (equal? subset?) between L, NL, coNL,
P, NP, PSPACE?

- True (T), false (F) or
unknown (U)? Below, “any” should be understood as “every” (rather
than “some”).

1. The
complement of any language in P is also in P.

2. The
complement of any language in NL is also in NL.

3. The
complement of any language in NP is also in NP.

4. The
complement of any language in PSPACE is
also in PSPACE.

5. Any
language that is both in NP and coNP is
decidable in polynomial time.

6. Every
regular language is decidable in linear time.

7. No EXPSPACE-complete language is in P.

8. PATH is in EXPTIME.