tag:blogger.com,1999:blog-3722233.post5971210651823745104..comments2023-09-21T05:17:55.889-05:00Comments on Computational Complexity: Theorems and Lemmas and Proofs, Oh My!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-80952571495827173832023-08-29T07:24:17.018-05:002023-08-29T07:24:17.018-05:00Yes! Many non-mathematicians don't know what a...Yes! Many non-mathematicians don't know what a definition is (even though the math meaning is one of the English meanings).David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37051973488044891822023-08-29T04:01:00.212-05:002023-08-29T04:01:00.212-05:00Also missing is "definition", this may s...Also missing is "definition", this may sound self evident but I actually once had a student ask me what the difference between a theorem and a definition is. <br /><br />The two can get quite close two each other, for example:<br /><br />Definition:<br />A function $f(x)$ is continuous if for all $a$ in it's domain $\lim_{x \to a} f(x) = f(a)$.<br /><br />Theorem:<br />All polynomials are continuous.<br /><br />In the student's mind, both cases defined something to be "continuous" and so he wondered why I called one a definition and the other a theorem.Robertnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73985208808053738932023-08-29T01:40:38.531-05:002023-08-29T01:40:38.531-05:00There are also laws: for example the law of large ...There are also laws: for example the law of large numbers and Muphry's Law.<br />David in Tokyonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24314258613252439982023-08-28T15:31:17.319-05:002023-08-28T15:31:17.319-05:00This comment has been removed by the author.Tim Conversehttps://www.blogger.com/profile/13246489031540721980noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31423087594419367212023-08-28T10:36:44.061-05:002023-08-28T10:36:44.061-05:00In this context, it is something we (e.g., the com...In this context, it is something we (e.g., the community) are going to accept, but we can't prove it because it refers to something that does not have a precise definition. <br /><br />I don't know if I'd include self-evident as being a usual property of an axiom. Axioms are things that we assume are true, so we don't have to list them in the hypotheses of a theorem. Some are more self-evident than others.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28434131316981055422023-08-28T02:01:16.092-05:002023-08-28T02:01:16.092-05:00Since you're asking for other hypotheses, ETH ...Since you're asking for other hypotheses, ETH (Exponential Time Hypothesis) would be one :)Isahttps://www.blogger.com/profile/06238608648470733216noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88050134964708201432023-08-28T01:25:55.976-05:002023-08-28T01:25:55.976-05:00A "thesis," as in the "Church-Turin...A "thesis," as in the "Church-Turing Thesis," is a statement which most people in the community agree to (have to) accept, for else they are considered part of some other community. Even anachronistically, then, Alan Turing arguably did not belong to the computer science community as we have come to understand it: https://link.springer.com/article/10.1007/s11023-023-09634-0<br /> Edgarhttps://www.blogger.com/profile/14255710142894208595noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40197950171107192552023-08-27T22:42:30.939-05:002023-08-27T22:42:30.939-05:00(Bill G) How would define `Thesis' in this con...(Bill G) How would define `Thesis' in this context? A statement that most people accept? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20161721536434105802023-08-27T21:27:14.985-05:002023-08-27T21:27:14.985-05:00There is also "thesis" as in "Churc...There is also "thesis" as in "Church's thesis". Is there another such use of "thesis"?David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28605901619530311472023-08-27T20:42:22.245-05:002023-08-27T20:42:22.245-05:00You left out Observation: a lemma with a very easy...You left out Observation: a lemma with a very easy proofD. Eppsteinhttps://www.blogger.com/profile/11923501729858669855noreply@blogger.com