## Marks 1

More
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
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected ...
GATE CSE 2013
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
GATE CSE 2009
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
The problems 3-SAT and 2-SAT are
GATE CSE 2004
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

## Marks 2

More
Consider the decision problem 2CNFSAT defined as follows: { $$\Phi$$ | $$\Phi$$ is a satisfiable propositional formula...
GATE CSE 2014 Set 3
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
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
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
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
Which of the following problems is not NP-hard?
GATE CSE 1992

### EXAM MAP

#### Graduate Aptitude Test in Engineering

GATE ECE GATE CSE GATE CE GATE EE GATE ME GATE PI GATE IN

#### Joint Entrance Examination

JEE Main JEE Advanced