1

GATE CSE 2004

MCQ (Single Correct Answer)

+1

-0.3

The problems 3-SAT and 2-SAT are

2

GATE CSE 2003

MCQ (Single Correct Answer)

+1

-0.3

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 Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?

Questions Asked from P and NP Concepts (Marks 1)

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