Re: Reductions in P

In article <1152982033.990753.270120@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<ahuznot@xxxxxxxxx> wrote:
Question: does it make any sense to reduce a problem P1 in P to another
P2 in P? If yes, what conclusion can I draw from such an reduction? I
don't see the point in reducing in P, because if both P1 and P2 have
poly-time algorithms, what knowledge can I extract from the fact that
there exists a poly-time reduction P1 \le_p P2?

You correctly see that there isn't much point in polytime reductions
between problems in P. To get an "interesting" reduction between problems
in P, the reductions in question have to have a complexity that is, at
least ostensibly, less than polytime. For example, logspace reductions
between problems in P are often considered.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Pythons simplicity philosophy
    ... you are reducing the number of numbers. ... useful reduction becomes even more important. ... Reducing a dimension 1 vector to a dimension 0 number is reduction in ... Perhaps my career in statistics and data reduction made reducemore ...
    (comp.lang.python)
  • Re: Sine code for ANSI C
    ... But doing proper argument reduction is an open ... Just reducing the argument modulo ... > many extra bits of precision. ...
    (comp.lang.c)
  • Reductions in P
    ... suffices to take a known NP-complete problem and reduce it to X, ... what conclusion can I draw from such an reduction? ...
    (comp.theory)
  • Re: UK age of consent
    ... David J wrote: ... >>would get away with a straightforward reduction, so they are reducing ... Prev by Date: ...
    (uk.legal)