tag:blogger.com,1999:blog-3722233.post1145574781456662669..comments2023-06-01T23:08:19.877-05:00Comments on Computational Complexity: P = NP and CancerLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-52344921461521321572018-10-25T06:28:27.586-05:002018-10-25T06:28:27.586-05:00I have the preprint in HAL which is equivalent to ...I have the preprint in HAL which is equivalent to arxiv<br /><br />https://hal.archives-ouvertes.fr/hal-01343812Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54811844311876132622018-10-11T07:50:15.937-05:002018-10-11T07:50:15.937-05:00I do not have endorsement. Upload by yourself if y...I do not have endorsement. Upload by yourself if you wish and keep me as the author, please. If you are gonna do it, share the link, please. I suggest to upload the P=NP proof which contains the UP=NP proof as well. Thanks in advance!!!Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44285135142044832842018-10-11T02:09:54.262-05:002018-10-11T02:09:54.262-05:00Just upload it to Arxiv.Just upload it to Arxiv.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3602152759302818672018-10-02T05:32:24.065-05:002018-10-02T05:32:24.065-05:00You could see my proof of UP=NP in
https://www.ac...You could see my proof of UP=NP in<br /><br />https://www.academia.edu/37430336/UP_versus_NP<br /><br />and see my proof of P = NP in<br /><br />https://www.academia.edu/37469408/P_versus_NP<br /><br />Thanks in advanceā¦Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49309889022445129772018-09-24T10:30:24.046-05:002018-09-24T10:30:24.046-05:00You could see my proof of UP=NP in
https://www.ac...You could see my proof of UP=NP in<br /><br />https://www.academia.edu/37430336/UP_versus_NP<br /><br />and see my proof of P = NP in<br /><br />https://www.academia.edu/37469408/P_versus_NP<br /><br />You could download them in Zenodo in the respective url:<br /><br />For UP=NP, we have<br /><br />https://zenodo.org/record/1434273<br /><br />For P=NP, we have<br /><br />https://zenodo.org/record/1434277<br /><br />In general, you could see my whole research in<br /><br />https://uh-cu.academia.edu/FrankVega<br /><br />Thanks in advanceā¦.Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80483545173904412692018-09-23T07:36:53.178-05:002018-09-23T07:36:53.178-05:00See my complete poof of UP = NP on
https://www.ac...See my complete poof of UP = NP on<br /><br />https://www.academia.edu/37430336/UP_versus_NP<br /><br />And you can download in<br /><br />https://zenodo.org/record/1433419#.W6eHVRnB8ewFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35354227307567040912018-09-21T12:44:56.455-05:002018-09-21T12:44:56.455-05:00The point being made is valid. A similar statement...The point being made is valid. A similar statement was proved a few years ago: that "physics is hard". That means if P=NP physics would be easy, with all of the engineering benefits of that.<br /><br />There is, however, a question about P=?NP that I have never seen seriously addressed, and I think should be. Bluntly, does the human brain solve NP problems, and does it do it in P? <br /><br />There are obvious technical issues with measuring how much computational work the brain does, but are there any non-trivally-small-N NP problems that the human brain is known to solve? Are problems like face recognition and such known to be in, or not in, NP? Does the brain, at best, only do a random "paratrooper" solution to non-convex problems, and arguably with an exponential amount of work?<br /><br />It would be interesting to know if A: not even the human brain can solve NP problems in P, or, alternatively, that the human brain does solve NP problems in P. One would think that that is an actual testable empirical fact that could be found out.<br /><br />Again, there are all sorts of technical problems to answering that question. One could say that Sudoku problems are NP, but that the human brain arguably supplies an exponential amount of power on them. One could also say that a lot of apparent NP problems (like Sudoku) are solved by human brains by relying on an exponential amount of memory of solved problems, and that the actual computation is minor. There is also the issue that the human brain my have trillions of cells, but that only a small percentage are devoted to actual computation, so judging the amount of power available is tricky. Still, the question should be answerable, and the answer would be interesting. <br /><br />There is also the problem of measuring the computational size in analogue systems. A (hypothetical) true Real space system has an arguably infinite computational capability. That is what makes solving problem with physical simulations so hard to use as computational models. To the extent that the brain uses continuously variable signals that would be another problem in looking at what problems the brain can solve and how much work it does in solving them.<br /><br />A look at animal models might be interesting, as they present smaller systems. Can an earthworm solve a (very small) NP problem? If no, is there a threshold in brain size that can? <br /><br />The obvious joke is that if the human brain could solve NP problems in P, it would have already settled the P=?NP issue. But that does not answer the question of if the human brain does solve some NP problems. A yes or no to that question would make the P=?NP question more interesting.<br />Anonymoushttps://www.blogger.com/profile/07279588979839719656noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47883499614960613062018-09-20T16:01:17.229-05:002018-09-20T16:01:17.229-05:00So according to Ryan Williams on Twitter SAT ist s...So according to Ryan Williams on Twitter SAT ist solvable now, but the next level of the PH requires exponential time. I guess this is not proven, just a new ETH. History might repeat itself, and maybe in 15 years Sigma2 SAT is solvable in practice and cancer will be cured after all.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74514444569152065632018-09-19T22:17:28.937-05:002018-09-19T22:17:28.937-05:00How many variables are in those problems?
(We do h...How many variables are in those problems?<br />(We do have kind of efficient SAT solvers.<br />But don't we need NP=LIN to handle those bio problems?)edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64705758895052002032018-09-17T11:46:23.303-05:002018-09-17T11:46:23.303-05:00You could see my proof of UP=NP in
https://www.ac...You could see my proof of UP=NP in<br /><br />https://www.academia.edu/37430336/UP_versus_NP<br /><br />and see my proof of P = NP in<br /><br />https://www.academia.edu/37431232/Sparse_complete_sets_for_coNP_Solution_of_the_P_versus_NP_problem<br /><br />You could download them in Zenodo in the respective url:<br /><br />For UP=NP, we have<br /><br />https://zenodo.org/record/1419750#.W55I5xnB8ew<br /><br />For P=NP, we have<br /><br />https://zenodo.org/record/1420486#.W5_TC9JKjIU<br /><br />In general, you could see my whole research in<br /><br />https://uh-cu.academia.edu/FrankVega<br /><br />Thanks in advance....Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47652141085194499362018-09-15T17:09:55.596-05:002018-09-15T17:09:55.596-05:00Ty, that really helped.Ty, that really helped.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40303336235502764192018-09-15T01:47:06.564-05:002018-09-15T01:47:06.564-05:00As with most decision problems, complexity for SAT...As with most decision problems, complexity for SAT is conventionally measured in terms of the length of the input. This is roughly O(clauses * log(variables)). Some authors use 'n' for the number of variables though, so in actual papers you want to check the definitions. It rarely matters in casual contexts, since SAT problems with very low or very high clause/variable ratios are generally easy.Aaron Rotenberghttp://aaronrotenberg.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50352230692441806062018-09-14T13:39:38.243-05:002018-09-14T13:39:38.243-05:00This article sounds just about as ridiculous to bi...This article sounds just about as ridiculous to biologists as it does to quantum computing folks when people with no background talk about their field...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14497691267679501082018-09-14T07:33:39.663-05:002018-09-14T07:33:39.663-05:00So we keep mentioning the efficiency of the algori...So we keep mentioning the efficiency of the algorithm in terms of the input size (n), but what defines (n) for SAT ? Is it the number of clauses ? Is is the number of total variables ? Which one of them ? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88347005512538237332018-09-13T22:07:43.750-05:002018-09-13T22:07:43.750-05:00n-body simulation is PSPACE-complete and thus no g...n-body simulation is PSPACE-complete and thus no guarantee that P=NP (even a linear time algorithm) would mean we can simulate the folding of proteins quickly (https://en.wikipedia.org/wiki/N-body_simulation#Computational_complexity).<br /><br />And even if we could, no guarantee that we can actually so precisely target cancer cells using just proteins in the first place.Siddharthahttps://www.blogger.com/profile/06497344734838391825noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76565037232020054852018-09-13T19:29:12.260-05:002018-09-13T19:29:12.260-05:00Why is it ill-informed? Elaborate ...Why is it ill-informed? Elaborate ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13315140607496504092018-09-13T10:26:13.834-05:002018-09-13T10:26:13.834-05:00Ill-informed articles such as this one are the rea...Ill-informed articles such as this one are the reason why Trump got elected.Anonymousnoreply@blogger.com