Question: Assume that problem Q_1 reduces to problem Q_2 in poly time and both Q_1 and Q_2 are in NP. (a) If Q_1 can be solved
Assume that problem Q_1 reduces to problem Q_2 in poly time and both Q_1 and Q_2 are in NP. (a) If Q_1 can be solved in polynomial time, what can be concluded about Q_2? (The answer may be nothing.) (b) If Q_2 can be solved in polynomial time, what can be concluded about Q_1? (The answer may be nothing.) (c) If Q_1 is NP-complete, what can be concluded about Q_2? (The answer may be nothing.) (d) If Q_2 is NP-complete, what can be concluded about Q_1? (The answer may be nothing.)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
