MCQ:

A)

A k-clique in a graph G is a set of k nodes of G such that there is an edge between every pair of nodes in the set. The problem k-CLIQUE is: Given a graph G and a positive integer k, does G have a k-clique?

We can prove k-CLIQUE to be NP-complete by reducing the 3SAT problem to it. Consider the 3-CNF expression:

E = (x₁' + x₂ + x₃)(x₁' + x₂' + x₃')(x₃ + x₄ + x₅')(x₁ + x₂ + x₄)

[Note: a' denotes the negation NOT(a) of variable a.] Let G be the graph constructed from this expression. Then, let H be the complement of G, that is, the graph with the same nodes as G and an edge between two nodes if and only if G DOES NOT have an edge between those two nodes. Let us denote the vertices of H by using the corresponding (clause, literal) pair. The node (i,j) corresponds to the j^th literal of the i^th clause. Which of the following nodes form a maximum-sized clique in H?

a) {(1,1),(2,1),(2,3),(3,2),(4,3)}

b) {(1,1),(1,3),(2,1),(4,3)}

c) {(1,1 ),(2,2),(3,3),(4,2)}

d) {(1,1), (2,1), (3,1), (4,3) }

-

B)

Suppose there are three languages (i.e., problems), of which we know the following:

1. L1 is in P.

2. L2 is NP-complete.

3. L3 is not in NP.

Suppose also that we do not know anything about the resolution of the "P vs. NP" question; for example, we do not know definitely whether P=NP. Classify each of the following languages as (a) Definitely in P, (b) Definitely in NP (but perhaps not in P and perhaps not NP-complete) (c) Definitely NP-complete (d) Definitely not in NP:

L1 L2.L1 [union] L2.

L2cL3, where c is a symbol not in the alphabet of L2 or L3 (i.e., the marked concatenation of L2 and L3, where there is a unique marker symbol between the strings from L2 and L3).

The complement of L3.

Based on your analysis, pick the correct, definitely true statement from the list below:

a) L2cL3 is definitely in NP.

b) The complement of L3 is definitely not NP-complete.

c) L1 [union] L2 is definitely in NP.

d) L1 L2 is definitely in P.