Editing Polynomial-time reduction (section)

==Defining complexity classes==
The definitions of the complexity classes '''NP''', '''PSPACE''', and '''EXPTIME''' do not involve reductions: reductions come into their study only in the definition of complete languages for these classes. However, in some cases a complexity class may be defined by reductions. If ''C'' is any [[decision problem]], then one can define a complexity class '''C''' consisting of the languages ''A'' for which <math>A \le_m^P C</math>. In this case, ''C'' will automatically be complete for '''C''', but '''C''' may have other complete problems as well.

An example of this is the complexity class <math>\exists \mathbb{R}</math> defined from the [[existential theory of the reals]], a computational problem that is known to be [[NP-hard|'''NP'''-hard]] and in '''[[PSPACE]]''', but is not known to be complete for '''NP''', '''PSPACE''', or any language in the [[polynomial hierarchy]]. <math>\exists \mathbb{R}</math> is the set of problems having a polynomial-time many-one reduction to the existential theory of the reals; it has several other complete problems such as determining the [[Crossing number (graph theory)|rectilinear crossing number]] of an [[undirected graph]]. Each problem in <math>\exists \mathbb{R}</math> inherits the property of belonging to '''PSPACE''', and each <math>\exists \mathbb{R}</math>-complete problem is '''NP'''-hard.<ref>{{citation|first=Marcus|last=Schaefer|contribution=Complexity of some geometric and topological problems|contribution-url=http://ovid.cs.depaul.edu/documents/convex.pdf|title=Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|volume=5849|pages=334–344|doi=10.1007/978-3-642-11805-0_32|year=2010|title-link=International Symposium on Graph Drawing|isbn=978-3-642-11804-3|doi-access=free}}.</ref>

Similarly, the complexity class [[GI (complexity)|'''GI''']] consists of the problems that can be reduced to the [[graph isomorphism problem]]. Since graph isomorphism is known to belong both to '''NP''' and co-[[AM (complexity)|'''AM''']], the same is true for every problem in this class. A problem is '''GI'''-complete if it is complete for this class; the graph isomorphism problem itself is '''GI'''-complete, as are several other related problems.<ref>{{citation
 | first1 = Johannes | last1 = Köbler
 | first2 = Uwe | last2 = Schöning | author2-link = Uwe Schöning
 | first3 = Jacobo | last3 = Torán
 | title = The Graph Isomorphism Problem: Its Structural Complexity
 | publisher = Birkhäuser
 | year = 1993
 | isbn = 978-0-8176-3680-7
 | oclc = 246882287}}.</ref>