http://www.csc.villanova.edu/~japaridz/SDU2013/

Computability and
Complexity

2013-08-05 至 2013-08-16

*Instructor*** :**
Giorgi Japaridze

** Office Hours:** By appointment

*Grading*** :**
There will be an examination on August 21, 9:00-11:00 AM. No books, notes,
computers, cellular phones etc. will be allowed during it.

*Textbook**:**"Introduction to the Theory of Computation"* by
Michael Sipser. Cengage Learning,
2013. ISBN 978-1-133-18779-0 (3^{rd} edition; the earlier editions are
also fine, except that there can be some discrepancies in the numbering of
theorems, definitions and exercises). Having this textbook is not necessary,
but may be helpful.

*Lecture Notes:*

**The
Church-Turing Thesis** (Chapter 3)

**Decidability**
(Chapter 4)

**Reducibility**
(Chapter 5)

**Measuring
Complexity** (Section 7.1)

**The Class
P** (Section 7.2)

**The Class
NP** (Section 7.3)

**NP-Completeness**
(Section 7.4)

**Additional
NP-Complete Problems** (Section 7.5)

**Space
Complexity** (Section 8.0)

**Savitch's Theorem** (Section 8.1)

**The Class PSPACE** (Section 8.2)

**PSPACE****-Completeness** (Section 8.3)

**The
Classes L and NL** (Section 8.4)

**NL-Completeness**
(Section 8.5)

**NL Equals coNL** (Section 8.6)

**Hierarchy
Theorems** (Section
9.1)

**Relativization** (Section 9.2)

**Circuit
Complexity** (Section
9.3)

**Approximation
Algorithms** (Section
10.1)

**Probabilistic
Algorithms** (Section
10.2)

**Alternation** (Section 10.3)

**Interactive
Proof Systems** (Section
10.4)

**Parallel
Computation** (Section
10.5)

*Covered material and sample questions that could be
asked on the examination:*

(60%-90% of the examination questions will
come from this list)

**[August 5]** Slides
3.0.a – 3.2.a.

- Complete the following definitions, assuming that
is a Turing machine and*M*is a language over an alphabet*L*: (1)*S*is a*M*iff ... (2)*decider**M**recognizes**L**M**decides*iff ...*L* - Construct a TM that decides the language
**{0,11,10}**. Then turn it into a TM that recognizes but does not decide this language. - 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
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 }**|**(note: this is similar to but NOT the same as the example on slide 3.1.f).*n*>*m*} - 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).

**[August 6]** Slides 3.2.e – 5.1.a.

- 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.
- 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 the point).
- Exercise 3.7.
- What language does the universal Turing machine
recognize and how does it work?
- Theorems 4.11, 4.23, 5.1 with proofs.
- Prove that if a language
and its complement*L*are both recognizable, then__L__is decidable (Hint: the idea/insights can be found in the proof of Theorem 4.23).*L* - Prove that the halting problem is recognizable (Hint:
similar to the theorem on Slide 4.2.a).

**[August 7]** Slides 5.3.a – 7.2.f (7.2.g
has been omitted and will not be asked).

- Theorems 5.22, 7.14, 7.15 with proofs.
- 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}**.

*A***={**the length of*w*|is even*w***}**,the length of*B*={*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).
- Definitions 7.1, 7.2,
7.5, 7.7, 7.9, 7.12.
- Exercises 7.1, 7.2, 7.3, 7.8, 7.9 (“clique” is
explained on page 295).
- 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.

** [August 8]** Slides 7.3.a – 7.4.i

- Definitions 7.18, 7.19, 7.21, 7.29.
- Theorems (with proofs) 7.20, 7.24, 7.25, 7.31, 7.32.
- 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).
- Why is SAT in NP? (a brief justification).

** [August 9]** Slides 7.4.j, 7.5.a – 7.5.o (Slides 7.4.k – 7.4.v and 7.5.p
– 7.5.s omitted)

- Definition 7.34.
- Theorems (with proofs) 7.35, 7.36.
- Theorem 7.37 and Corollary 7.42 withOUT
proofs.
- Why is SAT in NP? (a brief
justification).
- Theorem (with proof) 7.44.
Since this proof is long, any part of it may be asked on the examination,
such as (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**, and (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) - Theorem (with proof) 7.46.
Since this proof is long, any part of it may be asked on the examination,
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** - Theorem (with proof) 7.55.

**[August 12]** Slides 8.0.a – 8.3.b

- Definitions 8.1, 8.2, 8.6, 8.8.
- Show that
**SAT**is decidable in linear space (Example 8.3). - Savitch's theorem with proof.
- What do we know and do not know about the relations
(equal? subset?) between P, NP, PSPACE, NPSPACE, EXPTIME?

**[August 13]** Slides 8.3.c – 8.5.d (proof
idea for Theorem 8.9 on slide 8.3.c omitted)

- Definitions 8.17, 8.21, 8.22.
- Show that TQBF is in PSPACE.
- Exercises 8.3.
- Show that GG
**Î**PSPACE (Slide 8.3.j) - Apply the procedure given in the proof of Theorem 8.14
(the procedure for converting a quantified Boolean formula
**f**into a graph**G**such that**fÎ****TQBF**iff**G****Î****GG**) to the formula**f****=****$****x****"****y****$****z****[(xÚyÚ**__x__)**Ù****(yÚzÚz)****Ù****(xÚ**__y__Ú__z__)] - Show that
**{0**^{k}1^{k}| k**³0}****Î**L (Example 8.18). - Show that PATH
**Î**NL (Example 8.19). - Theorem (with proof) 8.23.

**[August 14]** Slides 8.5.e – 8.6.d

- Theorems and corollaries (with proofs) 8.25, 8.26, 8.27.

**[August 15]** Slides 9.1.a – 9.1.e (Slide 9.1.f,
and all subsequent materials, will be omitted)

- Theorems (with proofs) 9.3,
9.10.

**[August 16]** Review