https://complexityzoo.net/index.php?title=Complexity_Dojo&feed=atom&action=history Complexity Dojo - Revision history 2021-08-03T03:26:33Z Revision history for this page on the wiki MediaWiki 1.35.0 https://complexityzoo.net/index.php?title=Complexity_Dojo&diff=3&oldid=prev Admin: 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 &quot;major theorem&quot; 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]] &amp;isin; {{zcls|n|npc|NP-complete}}.<br /> * [[Complexity Dojo/Savitch's Theorem|Savitch's Theorem]]: {{zcls|n|nspace}}(f(n)) &amp;sube; {{zcls|d|dspace}}(f&amp;sup2;(n)), {{zcls|p|pspace}} = {{zcls|n|npspace}}<br /> * [[Complexity Dojo/Ladner's Theorem|Ladner's Theorem]] {{zcls|p|p}} &amp;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}} &amp;sube; {{zcls|p|p}}&lt;sup&gt;{{zcls|symbols|sharpp|#P}}&lt;/sup&gt;.<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