Editing Complexity class (section)

===Reductions===
{{See also|Reduction (complexity)}}
Many complexity classes are defined using the concept of a '''reduction'''. A reduction is a transformation of one problem into another problem, i.e. a reduction takes inputs from one problem and transforms them into inputs of another problem. For instance, you can reduce ordinary base-10 addition <math>x+y</math> to base-2 addition by transforming <math>x</math> and <math>y</math> to their base-2 notation (e.g. 5+7 becomes 101+111). Formally, a problem <math>X</math> reduces to a problem <math>Y</math> if there exists a function <math>f</math> such that for every <math>x \in \Sigma^* </math>, <math>x \in X</math> ''if and only if'' <math>f(x) \in Y</math>.

Generally, reductions are used to capture the notion of a problem being at least as difficult as another problem. Thus we are generally interested in using a polynomial-time reduction, since any problem <math>X</math> that can be efficiently reduced to another problem <math>Y</math> is no more difficult than <math>Y</math>. Formally, a problem <math>X</math> is polynomial-time reducible to a problem <math>Y</math> if there exists a ''polynomial-time'' computable function <math>p</math> such that for all <math>x \in \Sigma^*</math>, <math>x \in X</math> ''if and only if'' <math> p(x) \in Y</math>.

Note that reductions can be defined in many different ways. Common reductions are [[Cook reduction]]s, [[Karp reduction]]s and [[Levin reduction]]s, and can vary based on resource bounds, such as [[polynomial-time reduction]]s and [[log-space reduction]]s. 

====Hardness====
Reductions motivate the concept of a problem being '''hard''' for a complexity class. A problem <math>X</math> is hard for a class of problems '''C''' if every problem in '''C''' can be polynomial-time reduced to <math>X</math>. Thus no problem in '''C''' is harder than <math>X</math>, since an algorithm for <math>X</math> allows us to solve any problem in '''C''' with at most polynomial slowdown. Of particular importance, the set of problems that are hard for '''NP''' is called the set of '''[[NP-hard]]''' problems.

====Completeness====
If a problem <math>X</math> is hard for '''C''' and is also in '''C''', then <math>X</math> is said to be '''[[complete (complexity)|complete]]''' for '''C'''. This means that <math>X</math> is the hardest problem in '''C''' (since there could be many problems that are equally hard, more precisely <math>X</math> is as hard as the hardest problems in '''C'''). 

Of particular importance is the class of [[NP-complete|'''NP'''-complete]] problems—the most difficult problems in '''NP'''. Because all problems in '''NP''' can be polynomial-time reduced to '''NP'''-complete problems, finding an '''NP'''-complete problem that can be solved in polynomial time would mean that '''P'''&nbsp;=&nbsp;'''NP'''.