Specifically, suppose L and M are formal languages over the alphabets Σ and Γ, respectively. A polynomialtime manyone reduction from L to M is a function f : Σ^{*} → Γ^{*} which can be computed in polynomial time in the input size and has the property that
w\in L \Leftrightarrow f(w)\in M\qquad\mbox{for every } w\in\Sigma^*.</math>
If such a function f exists, we also say that "L is polynomialtime manyone reducible to M". This notion of reducibility is used in the standard definitions of several complexity classes, for instance NPcomplete, PSPACEcomplete and EXPTIMEcomplete.
There are other ways to formalize the intuitive idea of reducibility, for example polynomialtime Turing reductions and logarithmicspace manyone reductions[?].
Search Encyclopedia

Featured Article
