Talk:L-reduction

From Wikipedia, the free encyclopedia

I think that the property is false. we must write:

... there exists a polynomial ε-approximation algorithm for B then there also exists a polynomial δ-approximation algorithm for A where ...

[edit] You are correct.

The page has been fixed. Thanks for your comment :-)

Esoth, 26 May 2007, 22:23 CEST

[edit] Proof (or reference for the proof) of the property missing

Where is the proof/reference for that property? Note that the book of Papadimitriou just proves $\delta = \alpha \beta \epsilon / (1-\epsilon)$. —Preceding unsigned comment added by 130.149.15.224 (talk) 09:28, 8 April 2008 (UTC)

[edit] Improve definition

The definition could be improved by adding the correct quantifiers to the last two items: "for any instance $x$ of $A$" and "for any instance $x$ of $A$ and any feasible solution $y$ of $R(x)$".