Re: Reductions in P


as far as i know the most important thing if you prove and use
P-completeness is to show that a ploblem may be intrinsically
sequential.

What about the following situation: P1 in P, P2 in NP-complete.
Can I actually reduce P1 to P2 in poly-time?

P1 <=_p P2

I'd say that it is possible, since reduction can be read as
"P2 is not easier than P1". And since P2 in NP-complete,
and P1 in P, P2 certainly is not easier than P1.

.

Relevant Pages

  • NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... Maybe the original input to B was of size n, ... The reduction occurs in polynomial time, ...
    (comp.theory)
  • Re: NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... that cannot happen at all if it is to be a polytime reduction. ... reduction of one problem A to another B is really a way of solving A ...
    (comp.theory)