1
GATE CSE 2015 Set 2
+1
-0.3
Consider two decision problems $${Q_1},{Q_2}$$ such that $${Q_1}$$ reduces in polynomial time to $$3$$-$$SAT$$ and $$3$$-$$SAT$$ reduces in polynomial time to $${Q_2}.$$ Then which one of the following is consistent with the above statement?
A
$${Q_1}$$ is $$NP,$$ $${Q_2}$$ is $$NP$$ hard.
B
$${Q_2}$$ is $$NP,$$ $${Q_1}$$ is $$NP$$ hard.
C
Both $${Q_1}$$ and $${Q_2}$$ are in $$NP.$$
D
Both $${Q_1}$$ and $${Q_2}$$ are $$NP$$ hard.
2
GATE CSE 2013
+1
-0.3
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.

A
1 , 2 and 3
B
1 and 2 only
C
2 and 3 only
D
1 and 3 only
3
GATE CSE 2009
+1
-0.3
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
A
There is no polynomial time algorithm for $${\pi _A}$$
B
If $${\pi _A}$$ can be solved deterministically in polynomial time, then P = NP
C
If $${\pi _A}$$ is NP-hard, then it is NP-complete.
D
$${\pi _A}$$ may be undecidable.
4
GATE CSE 2006
+1
-0.3
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
A
R is NP-complete
B
R is NP-hard
C
Q is NP-complete
D
Q is NP-hard
GATE CSE Subjects
EXAM MAP
Medical
NEET