# 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?