CSC 8510: Homework
Policy: Homework will
not be graded, but the quizzes and examination will be
mainly based on your homework. Books or notes will not be allowed during the
quiz or exam.
[For
the quiz of January 24/25]
Material covered: Slides 0.a – 1.1.g
Questions:
- 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)
[For
the quiz of January 31/February 1]
Material covered: Slides 1.1.g –
2.1.b
Questions:
- Exercise 1.16 (a)
- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise 1.20 [Note:
here S stands
for a∪ b]
[For
the quiz of February 7/8]
Material covered: Slides 2.1.c –
3.1.h
Questions:
- Exercise
2.3 (a,b,c,d,e)
- Exercise
2.4 (in this exercise, wR means w read
from right to left)
- Exercise
2.9 (ignore the question on ambiguity)
- Exercise
3.1
- Exercise
3.5
- Complete
the following definitions: (1) A Turing
machine M is
a decider iff ... (2) A Turing
machine M recognizes a language LÍS* iff ... (3) A Turing machine M decides a
language LÍS* iff ...
- What
are the three components of a configuration?
- Construct
a Turing machine (provide a full diagram) for the language {#0n>0m | n>m} (note:
this is similar to but NOT the same as the example on slide 3.1.f).
[For
the quiz of February 14/15]
Material covered: Slides 3.1.i – 3.2.g
Questions
- 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", "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.
- Design a TMO that, on any input wÎ{0,1}*, outputs 0w.
[For
the quiz of February 21/22]
Material covered: Slides 3.2.h – 4.1.d
Questions
- 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.
- Show
that {P | P is a polynomial equation that has integral roots} (i.e., the problem of existence of
integral roots for polynomial equations, for which Hilbert wanted to find
a deciding algorithm) is recognizable. Hint: fix the
description given in Exercise 3.7 so that it is a legitimate recognizing
(albeit not deciding) algorithm for this problem.
- Exercise
4.1(a,b,c,e)
- Exercise
4.3
- Exercise
4.5
[For
the quiz of February 28/29]
Material covered: Slides 4.2.a – 5.3.b
Questions
- 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.
- Prove that the acceptance problem ATM = {<M,w> | M is a TM that accepts input string w} is
undecidable (Theorem 4.11)
- Prove that if a language L and
its complement are both recognizable, then L is decidable (Theorem 4.22)
- Prove that the problem {<M,w> | M is a TM that does
not accepts input string w} (the
complement of ATM)
is unrecognizable (Theorem 4.23)
- Prove that if a language is decidable, then so is its
complement.
- Prove that if two languages are both decidable, then so is
their intersection.
- Prove that if two languages are both recognizable, then so is
their union.
- Prove that the halting problem
is undecidable (Theorem 5.1).
- Prove that the halting problem
is recognizable.
- 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 is the
language described by 1*0*, B is
the language described by 01*0*
- 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}
[For
the quiz of March 13/14]
Material covered: Slides 5.3.c – 7.1.p
Questions
·
Definitions
7.1, 7.7, 7.9.
· 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.
·
Explain
why every regular language is in TIME(n).
·
Theorems
(with proof ideas) 7.8, 7.11.
[For
the quiz of March 20/21]
Material covered: Slides 7.2.a-7.3.i
Questions
- Theorems (with proofs) 7.14, 7.15, 7.20, 7.24, 7.25.
- Exercises 7.8, 7.9,
7.10, 7.12
- Definitions 7.12, 7.18, 7.19, 7.21.
[For
the quiz of March 27/April 4]
Material covered: Slides 7.3.j – 7.4.k
(the proofs of Theorems 7.37 and 7.42 omitted: simply remember that both SAT
and 3SAT are NP-complete).
Questions
- 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).
- Definitions 7.28, 7.29,
7.34
- Theorems (with proofs) 7.31,
7.35, 7.36
- Exercise 7.5
- Show that if a language is in P, then so is its complement. Can
we say the same about NP? Explain your answer.
- Show that if two languages are in P, then so is their union.
- Show that if two languages are in P, then so is their
concatenation.
- Show that if two languages are in NP, then so is their union.
- Show that if two languages are in NP, then so is their
concatenation.
- Remember the procedure of polynomial time reduction of
3SAT to CLIQUE from the proof of the NP-completeness of CLIQUE (Theorem
7.32). It converts a 3cnf-formula φ into a <G,k> such
that φ is
satisfiable iff the graph G has a clique of size k. Apply that procedure to the
formula φ = (x∨y∨z) ∧ (x∨y∨z) ∧ (y∨x∨y) and
construct the corresponding <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 φ is satisfiable, then G has a clique of size k; (3) why it is the case that
if G has a clique of
size k, then φ is satisfiable.
FINAL examination
dates: May 8/9. Usual time and place.