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 (3rd 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 M
is a Turing machine and L is a language over an alphabet S: (1) M is a decider
iff ... (2) M
recognizes L iff ... (3) M decides L iff ...
- 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 | n>m} (note:
this is similar to but NOT the same as the example on slide 3.1.f).
- 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", "g
is computable" and
"the graph of g"
(Slide 3.2.g).
- For a bit string w, NOT(w) means w
with all bits changed. For example, 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 L
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).
- 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 "mapping
reduction" and "mapping
reducible" (Slide 5.3.a).
- In each case below, find (precisely define) a
particular function that is a mapping reduction of A to B.
Both A
and B
are languages over the alphabet {0,1}.
- A={w
| the length of w is even}, B={w | the length of w is odd}
- A=B={w | the length of w is even}
- A={0,1}*, B={00,1,101}
- Prove
that if a language A
is mapping reducible to a language B
and B is recognizable, then A is recognizable (hint: very similar to
the proof of Theorem 5.22).
- 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(n2) 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.
- 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) and construct the
corresponding graph.
- 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 is
satisfiable.
- 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)] and construct the
corresponding graph.
- Show that {0k1k
| 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