CS254 Spring 2003Practice Midterm 2
The practice midterm is below. Here are some facts about the actual
midterm: (a) The midterm will be in class . (b) It is
closed book, closed notes. Nothing will be permitted on your desk except
your pen (pencil) and test. (c) You should bring photo ID.
(d) There will be more than one version of the test. Each version
will be of comparable difficulty. (e) If your cell-phone or beeper
goes off you will be excused from the test at that point and graded
on what you have done till your excusal. (f) One problem (less typos)
on the actual test will be from the practice test.
1. The monotone circuit value problem (MCVP) is the circuit value problem
restricted to circuits without NOT gates. Show MCVP is P-complete with
respect to logspace reductions.
2. A database table is arranged into columns called attributes and has
rows of data. Given two sets of attributes X and Y, a functional dependency X-->Y holds between them
if whenever we fix the values of X and look at rows in the table
with those values of X they will all have the same values of Y. Given a
table T and a set of functional dependencies FD a key is a minimal set
X that fixes the set of all the attributes in the table. Show the problem
of figuring out whether a table T with functional dependencies FD has a
key of size less that k is NP-complete.
3. Prove there are no P-complete problems under linear time reductions.
4. A k-coloring of a graph G=(V,E) is a
function f: V--> 1...k such that if (i,j) is an edge in E then
f(i) =/= f(j). Show the problem of determining whether a graph G has a
subgraph of m vertices (that has all the edges from the original graph on
these vertices) which is 3-colorable is NP-complete.
5. Let F be a Boolean expression and let t be a truth assignment for
a set X of some but not neccessarily all of F's variable. Consider the
problem of determining whether every satisfying assignment of F assigns
the variables in X the same way t did. Show this problem is coNP-complete.
6. Describe what a Pratt certificate for primality consists of.
7. Suppose we are given a black box that solves the CLIQUE problem and
that a turing machine can use this black box by writing an instance of
CLIQUE to a special tape and entering a new state called QUERY. In one
time step the black box outputs after this instance on this special tape
the symbol y if the answer to the clique problem was YES and n if the
query did not make sense or if the answer to the CLIQUE problem was no.
Show how to use the blackbox to give a p-time algorithm to find a CLIQUE
of size n/2 in a graph of size n if such a CLIQUE exists.
8. Let X be a random variable assuming only nonnegative values. Prove
Markov's Inequality (a variation on Lemma 11.2): Pr(X >= t) <=
E(X)/t.
9. Show that PP is close under logspace many-one reductions.
10. Let PPTIME(f(n)) be those language in PP accepted in time f(n).
Show PPTIME(n) is strictly contained in PPTIME(n3).
|