1
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?
A
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
B
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
C
The subset sum problem belongs to the class NP
D
The subset sum problem is NP-hard
2
GATE CSE 2006
MCQ (Single Correct Answer)
+2
-0.6
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 Hamiltonian cycle exists in such graphs. Which one of the following is true?
A
Both DHAM3 and SHAM3 are NP-hard
B
SHAM3 is NP-hard, but DHAM3 is not
C
DHAM3 is NP-hard, but SHAM3 is not
D
Neither DHAM3 nor SHAM3 is NP-hard
3
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
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?
A
P3 is decidable if P1 is reducible to P3
B
P3 is undecidable if P3 is reducible to P2
C
P3 is undecidable if P2 is reducible to P3
D
P3 is decidable if P3 is reducible to P2 's complement
4
GATE CSE 1992
MCQ (Single Correct Answer)
+2
-0.6
Which of the following problems is not NP-hard?
A
Hamiltonian circuit problem
B
The 0/1 Knapsack problem
C
Finding bi-connected components of a graph
D
The graph coloring problem
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP