tag:blogger.com,1999:blog-3722233.post1110572478221348469..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Understanding Machine LearningLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-59954794010086683912017-05-29T18:45:38.837-04:002017-05-29T18:45:38.837-04:00How are both statements together consistent? 1. &q...How are both statements together consistent? 1. "correctness proofs can still be unfeasibily long". 2. "proof assistant software such as HOL or Coq could parse it and convince you it is correct". Sorry do not understand implications of P=NPAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88446480977597892382017-05-14T12:55:09.948-04:002017-05-14T12:55:09.948-04:00Obviously correctness proofs can be unfeasibly lon...Obviously correctness proofs can be unfeasibly long. Those would also be among those explanations of program behavior that we cannot understand. I was addressing Lance's claim that:<br /><br />"What if P = NP? Would that help. Actually it would makes things worse. If you had a quick algorithm for NP-complete problems, you could use it to find the smallest possible circuit for say matching or traveling salesman but you would have no clue why that circuit works."<br /><br />My point was simple: if short understandable explanations of a circuit's behavior exist at all, then we could find those explanations under P=NP (with the usual caveats of low-order constants). So P=NP would arguably help, not make things worse.ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72875622394435538862017-05-07T23:00:32.783-04:002017-05-07T23:00:32.783-04:00https://www.youtube.com/watch?v=W5-Xb9fd4JMhttps://www.youtube.com/watch?v=W5-Xb9fd4JMAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16004917858026535132017-05-07T22:57:35.645-04:002017-05-07T22:57:35.645-04:00no, correctness proofs can still be unfeasibily lo...no, correctness proofs can still be unfeasibily long.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4312792742998433952017-05-07T01:17:26.031-04:002017-05-07T01:17:26.031-04:00A video in youtube with the explanation of my P ve...A video in youtube with the explanation of my P versus NP solution!!!<br /><br />https://youtu.be/40C40QCZRg0Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86856284534739945162017-04-27T11:54:31.804-04:002017-04-27T11:54:31.804-04:00I will remove the link http://vixra.org/pdf/1704.0...I will remove the link http://vixra.org/pdf/1704.0335v1.pdf and use instead:<br /><br />https://hal.archives-ouvertes.fr/hal-01509423/documentFrankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11362389673777786662017-04-25T13:02:51.140-04:002017-04-25T13:02:51.140-04:00Given a number x and a set S of n positive integer...Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.<br /><br />You could read the details in:<br /><br />http://vixra.org/pdf/1704.0335v1.pdfFrankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42566041749722530362017-04-18T10:00:14.982-04:002017-04-18T10:00:14.982-04:00To your list of reasons to care, I would add anoth...To your list of reasons to care, I would add another: that the problem of understanding which learning tasks are feasible for these methods is a fascinating and important one from a purely intellectual point of view.gowershttps://www.blogger.com/profile/11312457281302462824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88110207900772152772017-04-17T18:49:57.364-04:002017-04-17T18:49:57.364-04:00Lance concludes "… we're a long way from ...<b>Lance</b> concludes "… we're a long way from figuring out cause and effect in people."<br />--------------------<br />The NIH web site "ClinicalTrials.gov" provides a concrete overview of our present understanding of "cause and effect in people".<br /><br />For example, a search of clinical trials concerning "personality" and "therapy", restricted to <a href="https://clinicaltrials.gov/ct2/results?term=personality+AND+therapy&recr=Open" rel="nofollow">clinical trials presently recruiting volunteers</a>, yields a peer-reviewed listing — a listing that even can be <a href="https://clinicaltrials.gov/ct2/results/browse?term=personality+AND+therapy&recr=Open&brwse=cond_alpha_all" rel="nofollow">conveniently alphabetized</a> — of conditions in respect to which an understanding of "cause and effect in people" is objectively lacking.<br /><br /><b>Q</b> Are we to infer that cognitive scientists, complexity theorists, and psychiatric physicians soon will be reading each other's literature?<br /><br /><b>A</b> They already are! Not often in STEAM-history, does cross-pollination of trans-disciplinary ideas occur as vigorously, fertilely, dangerously, even distressingly, and none-the-less excitingly as at present.<br /><br /><b>Q</b> Does this mean that programmers increasingly are consciously acting as (informatic) therapists to their neural networks, and concomitantly, psychiatrists increasingly are consciously acting as (<a href="https://clinicaltrials.gov/ct2/show/record/NCT02134223?term=personality+AND+therapy&recr=Open&cond=%22Borderline+Personality+Disorder%22" rel="nofollow">epigenetic/connectomic</a>) programmers to their human clients?<br /><br /><b>A</b> For more-and-more STEAM-workers — young ones especially — the plain-and-simple answer is "yes (obviously)". <br /><br />Whether welcome or not (opinions differ, obviously), isn't this transformative unification empirically evident (nowadays) to pretty much everyone?John Sidleshttp://tinyurl.com/ISH-QIP-2017-rump-slidesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75958213356228022182017-04-17T17:31:35.392-04:002017-04-17T17:31:35.392-04:00If P=NP you could also find the shortest proof in ...If P=NP you could also find the shortest proof in your favorite formal system that the smallest possible circuit does what you wanted it to do, as well as any other claim you are wondering that may be true about the circuit. That proof might not be comprehensible to you, but it could be written in a format where proof assistant software such as HOL or Coq could parse it and convince you it is correct. So if P=NP (with feasible low constants) I think that would definitely help.ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.com