Question 1 |

The problem 3-SAT and 2-SAT are

both in P | |

both NP complete | |

NP -complete and in P respectively | |

undecidable and NP complete respectively |

Question 1 Explanation:

Question 2 |

Language L_{1} is polynomial time reducible to language L_{2}. Language L_{3} is polynomial time reducible to L_{2}, which in turn is polynomial time reducible to language L_{4}. Which of the following is/are true?

I. if L_{4} \in P, then L_{2} \in P

II. if L_{1} \in P or L_{3} \in P, then L_{2} \in P

III. L_{1} \in P, if and only if L_{3} \in P

IV. if L_{4} \in P, then L_{1} \in P and L_{3} \in P

I. if L_{4} \in P, then L_{2} \in P

II. if L_{1} \in P or L_{3} \in P, then L_{2} \in P

III. L_{1} \in P, if and only if L_{3} \in P

IV. if L_{4} \in P, then L_{1} \in P and L_{3} \in P

II only | |

III only | |

I and IV only | |

I only |

Question 2 Explanation:

Question 3 |

Consider two decision problems Q1,Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

Q1 is in NP, Q2 is NP hard. | |

Q2 is in NP, Q1 is NP hard | |

Both Q1 and Q2 are in NP . | |

Both Q1 and Q2 are NP hard |

Question 3 Explanation:

Question 4 |

Consider the decision problem 2CNFSAT defined as follows:

{ \phi | \phi is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, \phi =(x_{1} \vee x_{2}) \wedge (x_{1} \vee \bar{x_{3}}) \wedge (x_{2} \vee x_{4}) is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

{ \phi | \phi is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, \phi =(x_{1} \vee x_{2}) \wedge (x_{1} \vee \bar{x_{3}}) \wedge (x_{2} \vee x_{4}) is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

NP-Complete | |

solvable in polynomial time by reduction to directed graph reachability. | |

solvable in constant time since any input instance is satisfiable | |

NP-hard, but not NP-complete |

Question 4 Explanation:

Question 5 |

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique
in a given graph. In this scenario, which one of the following represents the correct Venn
diagram of the complexity classes P, NP and NP Complete (NPC)?

A | |

B | |

C | |

D |

Question 5 Explanation:

Question 6 |

Which of the following statements are TRUE?

1. The problem of determining whether there exists a cycle in an undirected graph is in P.

2. The problem of determining whether there exists a cycle in an undirected graph is in NP.

3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

1. The problem of determining whether there exists a cycle in an undirected graph is in P.

2. The problem of determining whether there exists a cycle in an undirected graph is in NP.

3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

1, 2 and 3 | |

1 and 2 only | |

2 and 3 only | |

1 and 3 only |

Question 6 Explanation:

Question 7 |

Assuming P \neq NP, which of the following is TRUE?

NP-complete = NP | |

NP-complete \cap P = \phi | |

NP-hard = NP | |

P = NP-complete |

Question 7 Explanation:

Question 8 |

Let \pi _{A} be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for \pi _{A}. | |

If \pi _{A} can be solved deterministically in polynomial time, then P = NP. | |

If \pi _{A} is NP-hard, then it is NP-complete. | |

\pi _{A} may be undecidable |

Question 8 Explanation:

Question 9 |

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

If X can be solved in polynomial time, then so can Y | |

X is NP-complete | |

X is NP-hard | |

X is in NP, but not necessarily NP-complete |

Question 9 Explanation:

Question 10 |

The subset-sum problem is defined as follows: Given a set S of n positive
integers and a positive integer W, determine whether there is a subset of S
Whose elements sum to W.

An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Q solves the subset-sum problem in polynomial time when the input is
encoded in unary | |

Q solves the subset-sum problem in polynomial time when the input is
encoded in binary | |

The subset sum problem belongs to the class NP | |

The subset sum problem is NP-hard |

Question 10 Explanation:

There are 10 questions to complete.