Consider two decision problems π1,π2 such that π1 reduces in polynomialβ¦
GATE Β· 2015 Β· CS Β· Set 2 Β· Computer Science & IT
Consider two decision problems π1,π2 such that π1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to π2. Then which one of the following is consistent with the above statement?
- A.
π1 is in NP, π2 is NP hard.
- B.
π2 is in NP, π1 is NP hard.
- C.
Both π1 and π2 are in NP .
- D.
Both π1 and π2 are NP hard.
Attempted by 94 students.
Sign up free to check your answer
Sign up freeLoading lessonβ¦