Consider a reduction of problem A to problem B. What is the most precise claim you
can make about problem B for each of the following situations?
a) A is NP-complete and the reduction is in polynomial time.
NP-hard. (At least as hard as NP-complete problem.)
b) A is in polynomial time and the reduction is also in polynomial time.
B could be anything.
c) A is NP-complete and the reduction is in Pspace.
B could be anything.
d) A is in nondeterministic polynomial time and the reduction is in polynomial time.
B is at least as hard as A, but nothing more can be said.
e) A requires exponential time and the reduction is in polynomial time.
B must requires polynomial time for deciding.
f) A is Pspace complete and the reduction is in Pspace.
B could be anything.
_______________________________________________________________________
Suppose you could reduce an NP complete problem to a polynomial time problem in
polynomial time. What would be the consequence?
What if the reduction required exponential time?
If we could reduce an NP-complete problem to a problem in P, then NP will
be equal to P. If the reduction required exponential time, then there is not
special consequence. (In fact any NP-complete problem can be reduced to
a polynomial time solvable problem using exponential time reduction.)
_______________________________________________________________________
No comments:
Post a Comment