GATE 2015 CS (CS2) – Question 26

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial time to Q2. Which conclusion is consistent with these reductions?

Q1 is in NP and Q2 is NP-hard
Q2 is in NP and Q1 is NP-hard
Both are in NP
Both are NP-hard

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Q1 is in NP and Q2 is NP-hard

Explanation

Because 3-SAT is in NP, a polynomial reduction Q1≤p3-SAT gives an NP verification method for Q1. Because 3-SAT is NP-complete, 3-SAT≤pQ2 establishes Q2 as NP-hard. It does not establish Q2 membership in NP or Q1 hardness. Thus A.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…
GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…
GATE 2015 CS (CS3) Q64 – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
GATE 2021 CS (CS2) Q49 – For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual…
GATE 2026 CS (CS1) Q17 – Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T…

All Asymptotic Analysis and Time/Space Complexity questions →