Reductions in P
- From: ahuznot@xxxxxxxxx
- Date: 15 Jul 2006 09:47:14 -0700
We know that if one wants to prove a problem X to be NP-complete,
suffices to take a known NP-complete problem and reduce it to X, by
means of a polynomial-time reduction.
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?
.
- Follow-Ups:
- Reductions in PSPACE
- From: sasha mal
- Re: Reductions in P
- From: Markus Triska
- Re: Reductions in P
- From: tchow
- Reductions in PSPACE
- Prev by Date: Re: Why LL(1) Parsers do not support left recursion?
- Next by Date: Re: Reductions in P
- Previous by thread: Why LL(1) Parsers do not support left recursion?
- Next by thread: Re: Reductions in P
- Index(es):