GATE CSE

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

Coming soon

BookmarksSoon

My progressSoon

Home
Previous Year
GATE
CSE
Algorithms
NP-Completeness

Back

GATE CSE previous year questions · Algorithms

NP-Completeness

6 questions

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

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

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

Back

GATE CSE previous year questions · Algorithms

NP-Completeness

6 questions

Filters & sort1

FiltersClear all

Year

2015 2014 2013 2012

Set

Set 1 Set 2 Set 3

GATE CSE 2015 | Set 2 | Question 26

NP-Completeness

MCQ1 mark

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 time to

Q_2

. Then which one of the following is consistent with the above statement?

Single correct

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

Use ← → to move

Questions

1 total

Correct Wrong Answer seen

FiltersClear all

Year

Set

Marks

Marks

Question type

Question type