1
GATE CSE 2015 Set 2
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
MCQ (Single Correct Answer)
+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
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12