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?

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.

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?

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?

Questions Asked from P and NP Concepts (Marks 1)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages