CSC 427: Theory of Computation 1
Final Wednesday, 3 May 2017
4:30 PM
This is a take home final. It will be released to all students and be due at
the date and time given above.
You are to work independently, you can reference materials, but be careful
if your answers too closely repeat publicly available sources, or I will not be
able to evaluate your own grasp of the materials.
The problems contain enough depth that it is always possible, regardless
of the materials referenced, for you to demonstrate personal competence on
the tested material.
Name:
Problem Credit
1
2
3
4
5
Total
CSC 427: Theory of Computation 2
1. The SATISFIABILITY problem is, given a collection of clauses, such
as,
{ (x1 ∨ x2 ∨ x3 ∨ x4), (x2 ∨ x3 ∨ x1), (x1 ∨ x4) }
assign values to all xi such that each clause evaluates true.
This problem reduces to 3-SAT, where each clause has exactly three
literals.
(a) Show how a single clause that is not in the proper 3-SAT form is
made by the reduction into several clauses each in proper 3-SAT.
In particular, show the reduction for the following clause:
x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ∨ x6
Name by yi any new variables introduced.
(b) Why does your reduction work? Why is the reduced collection of
clauses simultaneously satisfiable if and only if the original clause
is satisfiable?
CSC 427: Theory of Computation 3
2. The book gave the following reduction from 3-SAT to VERTEX-COVER:
For each variable x, create a “variable widget” of two nodes x and x
connected by an edge. For each clause x∨y∨z create a “clause widget”
of three nodes x, y and z connected in a triangle. Connect each node in
a clause widget with a node in a variable widget according to the vari-
able or negation of variable that the nodes represent. Set k = n+ 2m,
where n is the number of variables, and m is the number of clauses.
Draw the resulting VERTEX-COVER instance of the following 3-SAT
instance and find a vertex cover. Give the satisfying assignment implied
by that cover.
{ (x1 ∨ x2 ∨ x3), (x1 ∨ x2 ∨ x3), (x1 ∨ x2 ∨ x3),
(x1 ∨ x2 ∨ x3), (x1 ∨ x2 ∨ x3) }
CSC 427: Theory of Computation 4
3. Addition of two positive integers takes O(k) time by the standard addi-
tion algorithm, with k the total length of the representation in binary
of the integers.
The following recursive function M defines multiplication,
M(x, y) =
x for y = 1
2 ∗M(x, y/2) for y even
x+ 2 ∗M(x, (y − 1)/2) for y odd and not 1
for positive integers x and y.
For instance,
M(6, 5) = 6 + 2 ∗M(6, 2) = 6 + 2 ∗ 2 ∗M(6, 1) = 6 + 2 ∗ 2 ∗ 6 = 30.
Show that multiplication is in P-time by analyzing this algorithm. The
run time will be in Big-Oh notation as a function of k, the total length
of the representation in binary of the numbers.
CSC 427: Theory of Computation 5
4. The set of Turing Machines that accept nothing, ETM , is undecidable.
(a) If a set is undecidable, can it be both R.E. and co-R.E.? Give
proof.
(b) If a set is undecidable, can it be neither R.E. and co-R.E.? Give
an example.
(c) Is ETM R.E., co-R.E., or neither? Give proof.
CSC 427: Theory of Computation 6
5. Given an NP problem A, there is a non-deterministic TM such that if a
is in the language then there is at least one computation path leading
to accept, but if a is not in the language then no computation path
leads to accept.
An important class of problems inside NP is Randomized Polynomial
Time, or RP. A problem is in RP if for a in the language then a pro-
portion of at least 1/100 of all computation paths are paths leading to
accept, and for a not in the language, there are no computation paths
leading to accept.
A Randomized Turing Machine is a deterministic Turing Machine that
in addition to the tape contents to guide the transitions, can flip a coin
and use the coin outcome to guide the transitions. The output of these
machines has an associated probability, which is the probability that
the coin flips will lead the computation to that output.
Prove the following:
For all problems in RP, there is a Randomized Turing Ma-
chine such that, if a is not in the language, the machine
rejects always, if a is in the language, the machine accepts
with probability 1− � and and rejects with probability �, for
any real � > 0.
While the class RP seems strange, it has practical significance. RP
problems are those NP problems for which one can trade not being
able to know the answer with being able to know the answer, but there
is a slim chance that the answer is wrong.