Editing Polynomial-time reduction (section)

==Completeness==
A [[complete problem]] for a given complexity class '''C''' and reduction ≤ is a problem ''P'' that belongs to '''C''', such that every problem ''A'' in '''C''' has a reduction ''A'' ≤ ''P''. For instance, a problem is [[NP-complete|'''NP'''-complete]] if it belongs to [[NP (complexity)|'''NP''']] and all problems in '''NP''' have polynomial-time many-one reductions to it. A problem that belongs to '''NP''' can be proven to be '''NP'''-complete by finding a single polynomial-time many-one reduction to it from a known '''NP'''-complete problem.<ref>{{citation|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|first1=Michael R.|last1=Garey|author1-link=Michael Garey|first2=D. S.|last2=Johnson|author2-link=David S. Johnson|publisher=W. H. Freeman|year=1979}}.</ref> Polynomial-time many-one reductions have been used to define complete problems for other complexity classes, including the [[PSPACE-complete|'''PSPACE'''-complete]] [[Formal language|languages]] and [[EXPTIME|'''EXPTIME'''-complete]] languages.<ref>{{citation|contribution=Complexity theory|pages=241–267|first=A. V.|last=Aho|authorlink=Alfred Aho|title=Computer Science: The Hardware, Software and Heart of It|doi=10.1007/978-1-4614-1168-0_12|year=2011|editor1-first=E. K.|editor1-last=Blum|editor2-first=A. V.|editor2-last=Aho|isbn=978-1-4614-1167-3|doi-access=free}}. See in particular p.&nbsp;255.</ref>

Every decision problem in [[P (complexity)|'''P''']] (the class of polynomial-time decision problems) may be reduced to every other nontrivial decision problem (where nontrivial means that not every input has the same output), by a polynomial-time many-one reduction. To transform an instance of problem ''A'' to ''B'', solve ''A'' in polynomial time, and then use the solution to choose one of two instances of problem ''B'' with different answers. Therefore, for complexity classes within '''P''' such as [[L (complexity)|'''L''']], [[NL (complexity)|'''NL''']], [[NC (complexity)|'''NC''']], and '''P''' itself, polynomial-time reductions cannot be used to define complete languages: if they were used in this way, every nontrivial problem in '''P''' would be complete. Instead, weaker reductions such as [[log-space reduction]]s or [[NC (complexity)|'''NC''']] reductions are used for defining classes of complete problems for these classes, such as the [[P-complete|'''P'''-complete]] problems.<ref>{{citation|last1=Greenlaw|first1=Raymond|first2=James|last2=Hoover|first3=Walter|last3=Ruzzo|year=1995|title=Limits To Parallel computation; P-Completeness Theory|isbn=978-0-19-508591-4}}. In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p.&nbsp;48.</ref>