tag:blogger.com,1999:blog-3722233.post1145574781456662669..comments2018-09-20T18:43:15.731-04:00Comments on Computational Complexity: P = NP and CancerLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-47883499614960613062018-09-20T17:01:17.229-04:002018-09-20T17:01:17.229-04: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-19T23:17:28.937-04:002018-09-19T23:17:28.937-04: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-17T12:46:23.303-04:002018-09-17T12:46:23.303-04: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-15T18:09:55.596-04:002018-09-15T18:09:55.596-04:00Ty, that really helped.Ty, that really helped.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40303336235502764192018-09-15T02:47:06.564-04:002018-09-15T02:47:06.564-04: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-14T14:39:38.243-04:002018-09-14T14:39:38.243-04: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-14T08:33:39.663-04:002018-09-14T08:33:39.663-04: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-13T23:07:43.750-04:002018-09-13T23:07:43.750-04: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-13T20:29:12.260-04:002018-09-13T20:29:12.260-04:00Why is it ill-informed? Elaborate ...Why is it ill-informed? Elaborate ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13315140607496504092018-09-13T11:26:13.834-04:002018-09-13T11:26:13.834-04: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