1
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.
2
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?
3
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?
4
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
The problems 3-SAT and 2-SAT are
Questions Asked from Marks 1
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization