Editing Reduction (complexity) (section)

==Examples==
* To show that a [[decision problem]] P is [[Undecidable problem|undecidable]] we must find a reduction from a decision problem which is already known to be undecidable to P. That reduction function must be a [[computable function]]. In particular, we often show that a problem P is undecidable by showing that the [[halting problem]] reduces to P.
* The complexity classes [[P (complexity)|P]], [[NP (complexity)|NP]] and [[PSPACE]] are closed under (many-one, "Karp") [[polynomial-time reduction]]s. 
* The complexity classes [[L (complexity)|L]], [[NL (complexity)|NL]], [[P (complexity)|P]], [[NP (complexity)|NP]] and [[PSPACE]] are closed under [[log-space reduction]].

===Detailed example===
The following example shows how to use reduction from the halting problem to prove that a language is undecidable. Suppose ''H''(''M'', ''w'') is the problem of determining whether a given [[Turing machine]] ''M'' halts (by accepting or rejecting) on input string ''w''. This language is known to be undecidable. Suppose ''E''(''M'') is the problem of determining whether the language a given Turing machine ''M'' accepts is empty (in other words, whether ''M'' accepts any strings at all). We show that ''E'' is undecidable by a reduction from ''H''.

To obtain a contradiction, suppose ''R'' is a decider for ''E''. We will use this to produce a decider ''S'' for ''H'' (which we know does not exist). Given input ''M'' and ''w'' (a Turing machine and some input string), define ''S''(''M'', ''w'') with the following behavior: ''S'' creates a Turing machine ''N'' that accepts only if the input string to ''N'' is ''w'' and ''M'' halts on input ''w'', and does not halt otherwise. The decider ''S'' can now evaluate ''R''(''N'') to check whether the language accepted by ''N'' is empty. If ''R'' accepts ''N'', then the language accepted by ''N'' is empty, so in particular ''M'' does not halt on input ''w'', so ''S'' can reject. If ''R'' rejects ''N'', then the language accepted by ''N'' is nonempty, so ''M'' does halt on input ''w'', so ''S'' can accept. Thus, if we had a decider ''R'' for ''E'', we would be able to produce a decider ''S'' for the halting problem ''H''(''M'', ''w'') for any machine ''M'' and input ''w''. Since we know that such an ''S'' cannot exist, it follows that the language ''E'' is also undecidable.