tag:blogger.com,1999:blog-3722233.post6668964187047699871..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: What is an Elegant Proof?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-65272945320978772232012-03-27T07:31:07.696-05:002012-03-27T07:31:07.696-05:00Here's a sketch:
Suppose that 10a+b=a²+b² ˂=˃...Here's a sketch:<br /><br />Suppose that 10a+b=a²+b² ˂=˃ b(b-1)=a(10-a) with<br />aϵ{1,...,9}, bϵ{0,1,...,9}.<br />Enumerating all possible cases we get:<br />For b(b-1) the set {9x8, 8x7, 7x6, 6x5, 5x4, 4x3, 3x2, 2x1, 1x0, 0x(-1)}<br />For a(10-a) the set {9x1, 8x2, 7x3, 6x4, 5x5, 4x6, 3x7, 2x8, 1x9}<br /><br />But the sets for b(b-1) and a(10-a) don’t have any value in common. Therefore there’s no 2-digits number that is the sum of the squares of its digits.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68791776017662988382012-03-26T22:16:13.638-05:002012-03-26T22:16:13.638-05:00The idea of counting the number of checks seems to...The idea of counting the number of checks seems to me partially a proxy for "are we doing something more clever than brute-force search?" In this latter formulation, this was one of the original motivations for P vs NP. Especially in the Russian school, NP problems were literally known as "perebor" or "brute-force" and the P vs NP problem was called the "problem of perebor." <br /><br />In this sense, and along the lines of what kl suggested, when one can attach a natural family of decision problems to a proof---that is, a family of statements, say parametrized by a natural number n, or any of the usual coterie of combinatorial objects we use in complexity---then one can ask about the complexity of the theorem-proving procedure for this family. Generically speaking, one might expect brute-force computer searches to be exponential, or NP at best, and more elegant techniques might lead to polynomial-time proofs/algorithms. <br /><br />Although we are often only interested in finit(ary) statements, we are also technically only ever interested in fint(ary) inputs to algorithms, and yet we still consider asymptotic complexity a good guide to something-like-efficiency. In the case of proofs, complexity in the usual sense (in addition to proof complexity proper) might perhaps offer at least a hint of elegance.Joshua Grochowhttp://people.cs.uchicago.edu/~joshuag/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56422454566223134232012-03-26T18:09:07.573-05:002012-03-26T18:09:07.573-05:00I may be an odd case, but I reject that a computer...I may be an odd case, but I reject that a computerized search is inherently inelegant. This is a belief that is bound to become more widespread as the role of computers increases in theorem proving. I think it's much more likely that a problem solvable by search is an inelegant problem.<br /><br />As Bill suggests, measuring the number of checks is a good proxy for elegance, at least in the case of human-readable proofs. If you allow that computer-aided proofs may be elegant, then we might want to expand that definition. Certainly, an elegant snippet of C code that runs quickly and solves the problem should be considered an elegant proof.<br /><br />Here is a more general proxy. For a solution to be elegant, consider the minimum over:<br /><br />1. Elegance of search code (that runs in "reasonable" time)<br />2. Length of computer-readable proof starting from scratch<br />3. Length of computer-readable proof depending on "natural" results, however deep<br />4. Program running time on a computer (of "reasonable" source complexity)<br />5. Inverse-elegance of human readable proof<br /><br />This revision still has a long way to go. In the case of 2, for instance, there may be computer-readable proofs that are short but take unintelligible leaps of logic. A similar situation occurs when a computer chess program arrives at a baffling but powerful move. Is such an unintelligible proof elegant? Maybe to a computer... Probably not to a human, at least right now.<br /><br />Item 3 would also give a proxy for measuring the elegance of the problem. Does it depend on a major result almost to the point that it is equivalent? Probably inelegant. Does it combine several deep results in a simple way? Probably elegant.<br /><br />klAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-798477560241839442012-03-26T16:45:16.426-05:002012-03-26T16:45:16.426-05:00Look at the equation 10a+b=a^2+b^2; has obvious so...Look at the equation 10a+b=a^2+b^2; has obvious solution a=10, b=0 in integers<br />40a+4b=4a^2+4b^2<br />(2a-10)^2+(2b-1)^2=101<br />101 is prime, 1 mod 4, hence there is a unique way to represent it as sum of two squares of natural numbers (Gauss primes), namely as 10^2+1^2 (coming from a=10,b=0), hence b=1 or 0, and a=0 or 10<br />How many checks is that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19198562108088397112012-03-26T16:30:58.333-05:002012-03-26T16:30:58.333-05:00But for a finitary process, there is ultimately no...But for a finitary process, there is ultimately no reason why anything holds. It is, at the end, nothing more than a coincidence.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14459281698932551572012-03-26T13:15:23.096-05:002012-03-26T13:15:23.096-05:00Actually, one could argue quite to the contrary th...Actually, one could argue quite to the contrary that, by enumeration, one learns nothing new about the structure, i.e.<br />after having checked all elements one knows wether they have <br />some property or not, but one did not gain any understanding why this is the case.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59874641376687433302012-03-26T12:07:49.032-05:002012-03-26T12:07:49.032-05:00Woops! I ammended the post and will fix the proof ...Woops! I ammended the post and will fix the proof later- I suspect<br />the theorem will really be the only numbers are 153, 370, 371, 407.<br />But I will see. <br /><br />THANKS!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63245750679078149032012-03-26T11:51:59.669-05:002012-03-26T11:51:59.669-05:00About the sum of the cubes problem: what about 370...About the sum of the cubes problem: what about 370, 371, and 407?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83608744199850735032012-03-26T10:29:05.993-05:002012-03-26T10:29:05.993-05:00A nice essay could be written comparing and contra...A nice essay could be written comparing and contrasting <i>elegant</i> proofs with <i>natural</i> proofs, with the former criterion regarded as a (mainly) algebraic aesthetic, and the latter as (mainly) a geometric one. As Grothendieck said of the latter:<br /><br />------<br /><i>“The unknown thing to be known appeared to me as some stretch of earth or hard marl, resisting penetration. . . the sea advances insensibly in silence, nothing seems to happen, nothing moves, the water is so far off you hardly hear it. . . yet it finally surrounds the resistant substance.”</i><br />------<br /><br />So is there a rarified class of proofs whose methods are <i>both</i> elegant and natural?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88037072131797043222012-03-26T08:45:32.155-05:002012-03-26T08:45:32.155-05:00In my opinion, if you have a completely finitary p...In my opinion, if you have a completely finitary process, then checking the elements one by one is the most elegant proof technique. The reason is that enumeration discovers all the structure, and exactly the structure, inherent in that finite set. Furthermore this process is a priori known to be correct and perfect.<br /><br />Using any set of more general axioms is a process that is only accidentally correct --- namely, perhaps there could be a tighter proof, but you were lucky and the axioms happened to cover the finite set closely enough.<br /><br />One should not confuse elegance with simplicity or conciseness.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.com