CS701 - Final Term Papers
Total questions were 7
1 Q MCQ’s having 15 parts (Very tricky)
6 Q’s Theory
Theory questions I remember are as follows:
1.
Why is it difficult to prove that P = NP or P 
NP? Do you think P is
equal to NP or not. Elaborate.
2.
Let DOUBLESAT=
{<Æ> | Æ has at least two satisfying assignments}. Show
that DOUBLE-SAT is NP-complete.
3.
Let A be the
language of properly nested parentheses. For example (()) and (()(()))() are in
A, but ) ( is not. Show that A is in L.
4.
For a
cnf-formula Æ with m variables
and c clauses, show that you can construct in polynomial time an N FA with
0(em) states that accepts all non satisfying assignments, represented as
Boolean strings of length m. Conclude that NFAs cannot be minimized in
polynomial time unless P == NP.
NP? Do you think P is
equal to NP or not. Elaborate.
1 Let
G represent and undirected graph. Also let LPATH = {<G,a,b,k>|G contains
a simple path of length k for a to b>}. Show that LPATH is NP complete.
2. prove cycle-
length problem is NL complete
3. A subset of
nodes of a graph is a dominating set if every other node of G is adjacent to
some node in the subset. Let DOMINATING-SET={<G, k> | G has a dominating
set with k nodes}. Show that it is NP-Complete by giving a reduction from
VERTEX-COVER.
4. Game of
balanced n unbalanced graph
5. QNFA Є PSPACE
