tag:blogger.com,1999:blog-3722233.post1382101806799648760..comments2022-12-06T13:57:54.224-06:00Comments on Computational Complexity: COMPUTER PROOF vs computer proof- Quadratic VDW theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-49419624164758391912018-05-26T20:15:43.092-05:002018-05-26T20:15:43.092-05:00Let f be computable function from N (set of natura...Let f be computable function from N (set of natural numbers) to {0, 1}. We try to define a decision problem Prob(f) as follows.<br />PROBLEM Prob(f).<br />For each finite set S, W_S() be a function from 2^S to {0, 1}. For subset A of S, let<br />W_Sf(A) = (1 - W_S(A))*f(|A|) + W_S(|A|).<br />Is there any subset B of S that W_Sf(B) = 0?<br />My question. Is the problem Prob(f) well-defined?<br />Anonymoushttps://www.blogger.com/profile/05214585390385502811noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29610104046550128572018-05-24T12:12:48.985-05:002018-05-24T12:12:48.985-05:00Lol ... the fascinating "Life and Works of Mr...Lol ... the fascinating "<a href="https://www.bookstellyouwhy.com/pages/books/55228/willard-r-espy/the-life-and-works-of-mr-anonymous" rel="nofollow">Life and Works of Mr. Anonymous </a>" has for centuries evoked the respect of all!John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25962756400483452292018-05-24T05:27:28.575-05:002018-05-24T05:27:28.575-05:00... nevertheless the compact Minizinc code:
array...... nevertheless the compact Minizinc code:<br /><br />array [1..58] of var 1..4 : c; constraint forall (a,d in 1..58 where a + d*d <=58) (c[a] != c[a+d*d]); solve satisfy;<br /><br />... has its own beauty :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17526924718813158902018-05-24T04:55:07.151-05:002018-05-24T04:55:07.151-05:00@John Sidles: I missed your legendary presence and...@John Sidles: I missed your legendary presence and responses. Nice to have you back. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67921786016686136862018-05-23T21:33:21.765-05:002018-05-23T21:33:21.765-05:00Final P vs NP efforts
http://vixra.org/abs/1805.0...Final P vs NP efforts<br /><br />http://vixra.org/abs/1805.0399Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50069038260302419422018-05-21T14:26:16.204-05:002018-05-21T14:26:16.204-05:00This post calls to mind Wendell Berry's essay ...This post calls to mind Wendell Berry's essay "Why I Am Not Going to Buy a Computer" (<i>Harpers</i>, 1988), the firestorm of criticism that essay evoked, and Berry's reply to that criticism in a subsequent essay "Feminism, the Body, and the Machine" (2003). <br /><br />Berry's "Why I Am Not Going to Buy a Computer" concluded:<br /><br />--------------<br />To make myself as plain as I can, I should give my standards for technological innovation in my own work. They are as follows: <br /><br />1. The new tool should be cheaper than the one it replaces. <br />2. It should be at least as small in scale as the one it replaces.<br />3. It should do work that is clearly and demonstrably better than the one it replaces.<br />4. It should use less energy than the one it replaces.<br />5. If possible, it should use some form of solar energy, such as that of the body.<br />6. It should be repairable by a person of ordinary intelligence, provided that he or she has the necessary tools.<br />7. It should be purchasable and repairable as near to home as possible.<br />8. It should come from a small, privately-owned shop or store that will take it back for maintenance and repair.<br />9. It should not replace or disrupt anything good that already exists, and this includes family and community relationships.<br />--------------<br /><br />The substitution "proof" for "tool" (etc.) yields:<br /><br />--------------<br />Whenever we seek to explain mathematics as plainly as we can, the following standards are appropriate: <br /><br />1. New proofs should be shorter than the ones they replace. <br />2. Their formalism should be simpler.<br />3. Their implications should be broader.<br />4. Their methods should require less training.<br />5. New proofs should occupy a natural place in the community of proofs.<br />6. They should checkable by a person of ordinary intelligence.<br />7. Their methods should be broadly taught.<br />8. The authors should assume responsibility for explaining new proofs, and if need be, repairing them.<br />9. New proofs should illuminate existing proofs and inspire further proofs.<br />--------------<br /><br />Well done, Mr. Berry! :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com