Home Previous Year GATE CSE

Menu

Home Previous Year

GATE CSE

All subjects Operating Systems132 DBMS122 Computer Networks142 Algorithms128 Programming & Data Structures195 Theory of Computation122 Compiler Design95 Computer Organization & Architecture131 Digital Logic91 Discrete Mathematics133 Engineering Mathematics139 General Aptitude260

Coming soon

BookmarksSoon

My progressSoon

PYQ Hub · Previous year questions, organised for practice.Every question lists its source.

NP-Completeness (Algorithms): GATE CSE PYQs | PYQ Hub

Operating Systems132

Computer Networks142

Programming & Data Structures195

Theory of Computation122

Compiler Design95

Computer Organization & Architecture131

Digital Logic91

Discrete Mathematics133

Engineering Mathematics139

General Aptitude260

Home
Previous Year
GATE
CSE
Algorithms
NP-Completeness

GATE CSE previous year questions · Algorithms

NP-Completeness

6 questions

Filters & sort1

Sort

FiltersClear all

Year

2015 2014 2013 2012

Set

Set 1 Set 2 Set 3

Marks

1

GATE CSE 2015 | Set 3 | Question 41

NP-Completeness

MCQ2 marks

Language

L_1

is polynomial time reducible to language

L_2

. Language

L_3

is polynomial time reducible to

L_2

, which in turn is polynomial time reducible to language

L_4

. Which of the following is/are true? I. if

L_4 \in P

, then

L_2 \in P

II. if

L_1 \in P

or

L_3 \in P

, then

L_2 \in P

III.

L_1 \in P

, if and only if

L_3 \in P

IV. if

L_4 \in P

, then

L_1 \in P

and

L_3 \in P

Single correct

Source: GATE CSE 2015 Set 3, IIT Kanpur. Official question paper and answer key.

2

GATE CSE 2014 | Set 1 | Question 38

NP-Completeness

MCQ2 marks

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

Figure for GATE CSE 2014 | Set 1 | Question 38

Single correct

Source: GATE CSE 2014 Set 1, IIT Kharagpur. Official question paper and answer key.

3

GATE CSE 2014 | Set 3 | Question 38

NP-Completeness

MCQ2 marks

Consider the decision problem 2CNFSAT defined as follows:

\{\Phi \mid \Phi \text{ is a satisfiable propositional formula in CNF with at most two literals per clause}\}

For example,

\Phi = (x_1 \lor x_2) \land (x_1 \lor \overline{x_3}) \land (x_2 \lor x_4)

is a Boolean formula and it is in 2CNFSAT. The decision problem 2CNFSAT is

Single correct

Source: GATE CSE 2014 Set 3, IIT Kharagpur. Official question paper and answer key.

Use ← → to move

Questions

3 total

Correct Wrong Answer seen

Sort

FiltersClear all

Year

2015 2014 2013 2012

Set

Set 1 Set 2 Set 3

Marks

Question type

Question type