tag:blogger.com,1999:blog-3722233.post1049864467650749308..comments2021-12-06T22:20:37.890-06:00Comments on Computational Complexity: What is an Elementary Proof?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-9475321995150557912010-02-14T01:32:26.440-06:002010-02-14T01:32:26.440-06:00In proof theory, a proof of a theorem from a set o...In proof theory, a proof of a theorem from a set of axioms is elementary iff the proof does not use concepts from outside of the axioms or the theorem, which technically means that all formulas appearing in the proof are subformulas of the axioms or the theorem. When one uses concepts from outside, one is usually defining new concepts representing complicated formulas and uses lemmas about these concepts (cut rule). By Gentzen's cut-elimination any proof can be made elementary, but the problem is that the size of the proof can grow super-exponentially, i.e. a one page proof can become 2^500/500 pages (assuming each page is around 500 letters). I am not even talking about 300-page proof of FLT. So size of an elementary proof is also important.<br /><br />Proof theoretic definition of an elementary proof (cut free proof) satisfies 1 and 3. If it is also short, then teaching it shouldn't be hard and therefore it will satisfy 2. And the only problem in finding this short proof is when one needs to find the right instances of terms needed in L\forall and R\exists rules, and that's probably the reason that a short elementary proof would not satisfy 4.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86561392731365897192010-02-12T11:01:33.489-06:002010-02-12T11:01:33.489-06:00Olivier Sudac's article is available online at...Olivier Sudac's article is available online at http://dx.doi.org/10.1016/S0304-3975(00)00116-X<br /><br />Did you mean to say that it should be <i>freely</i> available?AndrĂ¡s Salamonhttp://constraints.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28034614109494794712010-02-11T06:10:14.253-06:002010-02-11T06:10:14.253-06:00Elementary proof is an argument which looks rather...<i>Elementary proof is an argument which looks rather trivial in a developed theoretical context.</i><br /><br />While that would have been a perfectly fine definition, in fact <a href="http://en.wikipedia.org/wiki/Elementary_proof" rel="nofollow">elementary proof</a> already is somewhat vaguely defined, and it <i>does</i> just mean that the tools used in the proof are basic. As the link says, "some elementary proofs can be quite complicated".Elementarynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88283935164364494052010-02-11T02:45:38.624-06:002010-02-11T02:45:38.624-06:00It is important to distinguish elementary proofs f...It is important to distinguish elementary proofs from elementary tools.<br /><br />Elementary <i>proof</i> is an argument which looks rather trivial in a developed theoretical context. At the same time, elementary <i>tools</i> often lead to non-elementary and unnatural proofs.<br /><br />E. g. in this respect, Grothendieck is a master of elementary proofs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11721061451634882072010-02-10T19:51:19.234-06:002010-02-10T19:51:19.234-06:00I like definition 3 best. 1 is a particular examp...I like definition 3 best. 1 is a particular example consistent with this. Definitions 2 and 4 are more like "easy" as opposed to "elementary." An "elementary" proof is one where the individual steps are simple, as opposed to relying on deep results.<br /><br />Put another way, a high-school student could check the proof, given time. It might still take a genius to find it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70449256749387462512010-02-09T16:46:36.854-06:002010-02-09T16:46:36.854-06:00Anything I can understand is elementary, and usual...Anything I can understand is elementary, and usually trivial. :)Anonymousnoreply@blogger.com