**CSC 8510-001: Homework Assignments**

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

**[January
16]**

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

**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
23]**

**Material covered:** Slides 1.2.d-1.4.c

**Assignment:**

- Exercise 1.16 (a)
- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise
1.20 [Note: here Σ stands for
*a*]*∪ b*

**[January
30]**

**Material covered:** Slides 2.1.a-3.1.g

**Assignment:**

- 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)
- Exercise
3.1
- Exercise
3.5
- Complete
the following definitions: (1) A Turing machine
is a*M*iff ... (2) A Turing machine*decider**M*a language*recognizes*∈Σ*L******iff ... (3) A Turing machine*M*a language*decides*∈Σ*L******iff ... - Construct
a Turing machine (provide a full diagram) for the language
**{#****0**^{n}**>****0**^{m }**|**(note: this is similar to but NOT the same as the example on slide 3.1.f).*n*>*m*}

**[February 6]**

**Material covered:** Slides 3.1.h-3.2.g

- Design a fragment of a TM which, from a state “Beg?”, goes to a state “Yes” or “No”, depending on whether the scanning head is 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 which, from a state “Go to the beginning”, takes the scanning head to beginning of the tape and goes to state “Done” (Slide 3.1.j).
- Design a fragment of a TM which, 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.
- 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**.

**[February 13]**

**Material covered:** Slides 3.2.h-4.2.a

- Prove that a function is computable iff its graph is decidable (Slide 3.2.h).
- 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? (i.e., state the algorithm that it follows) Answers to both questions are found on Slide 4.2.a
- Theorems 4.1, 4.2, 4.4 with proofs.

**[February 20]**

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

**Assignment:**

- Prove that A
_{TM}, i.e. the acceptance problem for Turing machines, is undecidable (Theorem 4.11)

- Prove that the complement of A
_{TM}, i.e. the non-acceptance problem for Turing machines, is unrecognizable (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 particular function which is a mapping reduction of the acceptance problem to the halting problem (this is function f of Slide 5.3.d).

**[February 27]**

**Material covered:** Slides 7.1.a-7.1.p

**Assignment:**

- Definitions 7.1, 7.2, 7.7, 7.9
- 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}) - Theorems (with proof ideas) 7.8, 7.11.

**[March 13]**

**Material covered:** Slides 7.2.a-7.3.g

**Assignment:**

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

**[March 27]**

**Material covered:** Slides 7.3.h-7.4.h

**Assignment:**

- Exercise 7.5.
- Definitions 7.28, 7.29.
- Theorems
(with proofs) 7.24, 7.25, 7.31.

- 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).
- Remember the procedure given in the proof of Theorem 7.32 --- the procedure for converting a
3cnf-formula
**φ into a <****G,k>**such that φ∈**3SAT**iff <**G,k>**∈CLIQUE**. Apply it to the formula φ****= (**x∨y∨z**) ∧****(**∨__x__**y**∨**z)****∧****(y**∨*x*∨y**)****G,k>**.

- From the proof of Theorem 7.32, you should know and be
able to write in general terms (not merely examples) about: (1) how to
construct
**<G,k>**from φ; (2) why it is the case that if φ**G**has a clique of size**k**.

**[April 10]**

**Material covered:** Slides 7.4.i-7.4.k, 7.5.a-7.5.k

**Assignment:**

- From the proof of Theorem 7.32, you should know and be
able to write in general terms (not merely examples) about: (1) how to
construct
**<G,k>**from φ; (2) why it is the case that if φ**G**has a clique of size**k**; (3) why it is the case that if**G**has a clique of size**k,**then - 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 φ; (2) why it is the case that if φ**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 φ - Remember the procedure given in the proof of Theorem 7.46 --- the procedure for converting a
3cnf-formula φ
**into a graph****G**such that φ**is satisfiable iff****G****=****(**x∨y∨z**) ∧****(**∨__x__**y**∨**z)****∧****(y**∨*x*∨y**)**

- From the proof of Theorem 7.46, you should know and be
able to write in general terms (not merely examples) about how to construct
**G**from φ .

**[April 17]**

**Material covered:** Slides 7.5.l-7.5.o, 8.0.a-8.1.a, 8.2.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 φ**G**has a Hamiltonian path, and (3) why it is the case that if**G**has a Hamiltonian path, then φ 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? (no proof required)
- What do we know and do not know about the relations (equal? subset?) between P, NP, PSPACE, NPSPACE, EXPTIME?
- Exercise 8.2.

**[April 24]**

**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**

Examination on May 1; comprehensive, including the present material.

**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**≥ 0}^{k}1^{k}| k**∈ L (Example 8.18).** - Show
that PATH
- 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.