## Marks 1

More
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction fro...
GATE CSE 2003
The problems 3-SAT and 2-SAT are
GATE CSE 2004
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 ...
GATE CSE 2006
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
GATE CSE 2009
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected ...
GATE CSE 2013
Consider two decision problems $${Q_1},{Q_2}$$ such that $${Q_1}$$ reduces in polynomial time to $$3$$-$$SAT$$ and $$3$$...
GATE CSE 2015 Set 2

## Marks 2

More
Which of the following problems is not NP-hard?
GATE CSE 1992
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the...
GATE CSE 2005
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be th...
GATE CSE 2006
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine ...
GATE CSE 2008
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this s...
GATE CSE 2014 Set 1
Consider the decision problem 2CNFSAT defined as follows: { $$\Phi$$ | $$\Phi$$ is a satisfiable propositional formula...
GATE CSE 2014 Set 3