1

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

+2

-0.6

Consider the decision problem 2CNFSAT defined as follows:

{ $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, $$\Phi = \left( {{x_1} \vee {x_2}} \right) \wedge \left( {{x_1} \vee {{\overline x }_3}} \right) \wedge \left( {{x_2} \vee {x_4}} \right)$$ is a Boolean formula and it is in 2CNFSAT.The decision problem 2CNFSAT is

2

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

+2

-0.6

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a
given graph. In this scenario, which one of the following represents the correct Venn diagram of the
complexity classes P, NP and NP Complete (NPC)?

3

GATE CSE 2008

MCQ (Single Correct Answer)

+2

-0.6

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 Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

4

GATE CSE 2006

MCQ (Single Correct Answer)

+2

-0.6

Let SHAM

_{3}be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM_{3}be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?Questions Asked from P and NP Concepts (Marks 2)

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