https://complexityzoo.net/index.php?title=Complexity_Dojo&feed=atom&action=historyComplexity Dojo - Revision history2021-08-03T03:26:33ZRevision history for this page on the wikiMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Dojo&diff=3&oldid=prevAdmin: 1 revision: Complexity zoo import.2012-11-18T03:10:19Z<p>1 revision: Complexity zoo import.</p>
<p><b>New page</b></p><div>{{CD-Menu}}<br />
<br />
<br />
In complexity theory, it isn't enough to say that something is impossible; you have to ''prove'' it. So here in the '''Complexity Dojo''', we introduce several major theorems and proof techniques that will go a long way.<br />
<br />
Of course, there are going to be disagreements as to what a "major theorem" is, so this is all in the opinion of the [[Christopher Granade|Tour Guide]] and any other contributors. The main focus, though, will be on theorems that illustrate important concepts more than on theorems which have a direct impact. If you feel that the list of theorems is somehow terribly deficient for the lack of a specific theorem, please add it!<br />
<br />
For those of you not used to mathematical proofs in general, here's some resources that may help:<br />
* One of the various textbooks on the subject, such as that by [http://books.google.com/books?id=j7xcHwAACAAJ Maddox].<br />
* [[Wikibooks:Mathematical Proof|Mathematical Proof]], a book on [[WikiBooks:Main Page|WikiBooks]]. (As of the time of this writing, it is woefully incomplete, but it should improve.)<br />
* Wikipedia entry on [[Wikipedia:Mathematical proof|Mathematical proof]].<br />
* [http://mathworld.wolfram.com/ MathWorld]'s definitions of [http://mathworld.wolfram.com/Proof.html Proof] and [http://mathworld.wolfram.com/Theorem.html Theorem]. Also good is the page on [http://mathworld.wolfram.com/ReductioadAbsurdum.html proof by contradiction].<br />
<br />
Of course, none of these resources can compare with taking a class that requires proofs (real analysis or complexity theory make good candidates), or a class directly about proofs.<br />
<br />
== Major Theorems ==<br />
* [[Complexity Dojo/Cook-Levin Theorem|Cook-Levin Theorem]]: [[Complexity Garden#SAT|SAT]] &isin; {{zcls|n|npc|NP-complete}}.<br />
* [[Complexity Dojo/Savitch's Theorem|Savitch's Theorem]]: {{zcls|n|nspace}}(f(n)) &sube; {{zcls|d|dspace}}(f&sup2;(n)), {{zcls|p|pspace}} = {{zcls|n|npspace}}<br />
* [[Complexity Dojo/Ladner's Theorem|Ladner's Theorem]] {{zcls|p|p}} &ne; {{zcls|n|np}} implies that {{zcls|n|npi|NP-intermediate}} problems exist.<br />
* [[Complexity Dojo/Blum Speedup Theorem|Blum Speedup Theorem]]: Some problems do not have optimal solutions.<br />
* [[Complexity Dojo/Impagliazzo-Widgerson Theorem|Impagliazzo-Widgerson Theorem]]: {{zcls|p|p}} = {{zcls|b|bpp}} unless {{zcls|e|e}} has sub-exponential circuits.<br />
* [[Complexity Dojo/Toda's Theorem|Toda's Theorem]]: {{zcls|p|ph}} &sube; {{zcls|p|p}}<sup>{{zcls|symbols|sharpp|#P}}</sup>.<br />
* [[Complexity Dojo/Natural Proofs|Natural Proofs]]<br />
<br />
== Proof Techniques ==<br />
* {{ns|Christopher Granade:Complexity Dojo|Diagonalization}}: Method of showing that an enumeration of a set is incomplete.</div>Admin