# P and NP Concepts · Algorithms · GATE CSE

Start Practice

## Marks 1

GATE CSE 2015 Set 2
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...
GATE CSE 2013
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 ...
GATE CSE 2009
Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?
GATE CSE 2006
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 ...
GATE CSE 2004
The problems 3-SAT and 2-SAT are
GATE CSE 2003
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and ...

## Marks 2

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