MCQ1 mark
Consider two decision problems such that reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to . Then which one of the following is consistent with the above statement?
Single correct
MCQ2 marks
Language is polynomial time reducible to language . Language is polynomial time reducible to , which in turn is polynomial time reducible to language . Which of the following is/are true?
I. if , then
II. if or , then
III. , if and only if
IV. if , then and
Single correct
MCQ2 marks
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)?
Single correct
MCQ2 marks
Consider the decision problem 2CNFSAT defined as follows:
For example, is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is
Single correct
MCQ1 mark
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.
Single correct
Answer key coming soon
MCQ1 mark
Assuming , which of the following is TRUE?
Single correct
Answer key coming soon
Use ← → to move