tag:blogger.com,1999:blog-3722233.post8116578564622534031..comments2023-10-01T07:37:32.894-05:00Comments on Computational Complexity: NP is HardLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-59559618108204547462018-10-16T09:46:32.194-05:002018-10-16T09:46:32.194-05:00See my proof of P = NP in
https://www.academia.ed...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-27938581843553246022018-05-11T09:28:28.055-05:002018-05-11T09:28:28.055-05:00My following paper has gained too much attention i...My following paper has gained too much attention in Academia.edu preprint server. It is right now one of the top papers of this site. Perhaps this is a good approach to a final solution: who knows? This is the Abstract and the URL link: <br /><br />P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This question was first mentioned in a letter written by John Nash to the National Security Agency in 1955. A precise statement of the P versus NP problem was introduced independently in 1971 by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity class is Sharp-P. Whether P = Sharp-P is another fundamental question that it is as important as it is unresolved. If any single Sharp-P-complete problem can be solved in polynomial time, then every NP problem has a polynomial time algorithm. The problem Sharp-MONOTONE-2SAT is known to be Sharp-P-complete. We prove Sharp-MONOTONE-2SAT is in P. In this way, we demonstrate the P versus NP problem.<br /><br />https://www.academia.edu/36428710/P_versus_NPFrank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42419988837164263362018-03-12T19:13:16.244-05:002018-03-12T19:13:16.244-05:00I should note that RJL had a change of heart when ...I should note that RJL had a change of heart when it struck us that any P=NP proof must embody a proof of strong circuit lower bounds, yet no strategies ever proposed seem to give any sign of awareness of this need: https://rjlipton.wordpress.com/2017/12/08/pnp-perhaps-i-change-my-mind/ (We still both believe factoring is classically tractable though.)KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55651811230171371042018-02-25T00:58:27.172-06:002018-02-25T00:58:27.172-06:00Meanwhile, my 8-years efforts for P vs NP:
http:/...Meanwhile, my 8-years efforts for P vs NP:<br /><br />http://vixra.org/abs/1801.0100YShttp://vixra.org/abs/1801.0100noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2265892308415480032018-02-25T00:11:53.113-06:002018-02-25T00:11:53.113-06:00Meanwhile, my 8-years efforts for P vs NP:
http:...Meanwhile, my 8-years efforts for P vs NP:<br /><br /> http://vixra.org/abs/1801.0100Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82955771557520688842018-02-24T17:15:36.540-06:002018-02-24T17:15:36.540-06:00What I find curious about NPI is that we _know_ it...What I find curious about NPI is that we _know_ it is non-empty, assuming P ≠ NP. On the other hand, under the same assumption, we are unable to prove that any *natural* problem is in NPI. Andras Faragohttp://www.utdallas.edu/~faragonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89791162684659227522018-02-23T22:01:11.038-06:002018-02-23T22:01:11.038-06:00If you haven't already, there has been a recen...If you haven't already, there has been a recent breakthrough regarding UGC, see<br />Subhash Khot, Dor Minzer, and Muli Safra:<br /><a href="https://eccc.weizmann.ac.il/report/2018/006/" rel="nofollow">Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion.</a> Electronic Colloquium on Computational Complexity (ECCC) 25: 6 (2018)<br /><br />Changed my view from "agnostic" to "almost certainly true".Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20052699630081184742018-02-23T21:51:05.146-06:002018-02-23T21:51:05.146-06:00I find the existence of NP-Intermediate problems j...I find the existence of NP-Intermediate problems just as obvious as P ≠ NP. Consider Graph Isomorphism. (On a side note, I don't think Babai's breakthrough is progress towards showing GI is in P but the converse!) If it in P, then it would be insane. On a side note, I conjuncture that is not in BQP either. And by the beautiful result of Boppana, Hastad and Zachos, if GI is NP-Complete than the polynomial hierarchy collapses. (I know, I know, using the fact that polynomial hierarchy is infinite to give evidence that P ≠ NP is circular but think about it!)<br /><strong>Proving</strong> that a problem is NP-Intermediate is insanely hard, because it is (as you mentioned) equivalent to proving P ≠ NP.Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52001360359194024142018-02-23T17:52:34.640-06:002018-02-23T17:52:34.640-06:00RW is Ryan Wiliams, EJ is Anonymous, but a specifi...RW is Ryan Wiliams, EJ is Anonymous, but a specific anonymous. Obviously I am not very inside, otherwise I would have talked about Alice and Bob instead. How to explain background to a question in few words, without getting complaints about all kinds of perceived misbehaviour? I don't know and don't care. I just ask what I want to know, and give some background if I believe that it is necessary or helpful.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42498893801656817262018-02-23T09:44:20.524-06:002018-02-23T09:44:20.524-06:00NP complete/hard problems are a contrived set beca...NP complete/hard problems are a contrived set because real world "noise" in problem formulation imposes an upper bound way before we would hit the computational upper bound especially given the massive hardware resources that are readily available at our fingertips. <br /><br />To take Euclidean TSP as one prototypical example (yes, there is a trivial factor-of-2 approximation), I do not know of a situation where one possesses perfect data for the edge costs across M sites (M>100 or whatever is the upper bound of the best TSP solver) to begin planning. By the time we traverse a small fraction of the computed plan (say a Lyft or Uber autonomous car picking up passengers), the subsequent costs would have changed significantly to require re-planning every so often. While the exact TSP solution has proven optimality, it may be very sub-optimal (fragile) when considering an ever changing environment.<br /><br />Despite optimal chip design being another prototypical NP hard instance we now have incredible chips that incorporate many billions of transistors without breaking a sweat (at least not mine :-)). <br /><br />While NSA would love to crack encrypted data, they probably have figured out alternative schemes to get what they need - in many, if not all situations.<br /><br />Chess, go and other games are already contrived in that no one really cares how well you can play on an ever increasing NxN board. space2001noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40567666619232246232018-02-23T08:17:09.567-06:002018-02-23T08:17:09.567-06:00is it a mega name drop level where they don't ...is it a mega name drop level where they don't just drop the name they drop the initials showing just how inside they are?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9502794643350870832018-02-23T04:45:36.446-06:002018-02-23T04:45:36.446-06:00"And we've seen no non-trivial algorithms..."And we've seen no non-trivial algorithms for general NP problems like circuit-SAT."<br /><br />What counts as a non-trivial algorithm? Does the simplex-algorithm count as a non-trivial algorithm? It works fine in practice, most of the time. Do the recent analog Max-SAT solvers (like <a href="https://arxiv.org/abs/1801.06620" rel="nofollow">this from 20 Jan 2018</a> or <a href="https://arxiv.org/abs/1710.09278" rel="nofollow">that</a> from <a href="http://memcpu.com/" rel="nofollow">MemComputing, Inc.</a> initially presented <a href="https://arxiv.org/abs/1512.05064" rel="nofollow">on 16 Dec 2015</a>) count as non-trivial algorithms? The inventors claim that it works fine in practice, but I admit that claims from startups should be taken with a grain of salt.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77248700999380990362018-02-23T04:25:08.754-06:002018-02-23T04:25:08.754-06:00Who is EJ? Who is RW? Are we supposed to guess? Who is EJ? Who is RW? Are we supposed to guess? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35685735131144050762018-02-22T18:45:41.140-06:002018-02-22T18:45:41.140-06:00If I would guess collapses that might happen, ... ...If I would guess collapses that might happen, ... what about ALogTime = L (where ALogTime is just uniform NC1)?<br /><br />There was a very specific reason why I asked this question to EJ end of last year (his answer: "While ALogTime = L is a possibility, I think it is not very likely."). My specific reason from back than has been reduced in the meantime to the difference between expression evaluation in (canonical) binary tree representation vs expression evaluation in (canonical) directed forest representation. I should be able to resolve the remaining "unclearness" myself, as soon as I find the time to do it. But after RW wrote that '... Estimated Likelihoods ...' paper, I just had to ask him too. And since I got no reply, asking that same question here is just too tempting for me.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13294028591295289622018-02-22T17:57:44.647-06:002018-02-22T17:57:44.647-06:00"TC0 captures constant-depth neural networks&..."TC0 captures constant-depth neural networks"<br /><br />That's not literally true by definition. Is there a formalization that makes it true? Even assuming 01 inputs, relu gates, and a signum at the top, I don't see it immediately right now.Dániel Vargahttps://www.blogger.com/profile/10626372642275036283noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5104980779421648852018-02-22T17:45:46.183-06:002018-02-22T17:45:46.183-06:00Thank you for responding to Emanuele's post.
...Thank you for responding to Emanuele's post. <br /><br />I would add that we (the TCS community) have a pretty clear conjectural view of the computational landscape and the foundation stone of that conjectural view is P != NP. <br /><br />Whereas, if P=NP, then we really don't have a good explanation for anything; vast swathes of complexity theory and essentially all of cryptography fly out the window. <br /><br />Is it possible that most of TCS is wrong? Sure, we can't rule it out. But I think someone promoting that idea should provide an alternative coherent theory. How do you explain why some problems seem harder than others? "We just haven't found the algorithm yet" is not very compelling.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38141998126731738582018-02-22T17:06:52.171-06:002018-02-22T17:06:52.171-06:00It is good to be agnostic about mathematical conje...It is good to be agnostic about mathematical conjectures. I found Viola's argument for P=NP, like Lance, cherry picking. Going beyond agnosticism and believing P=NP requires more than a few falsified conjectures for specific problems. Re UGC various people said/say various things but we have to wait for the truth. Patience is called for.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35355693518853339722018-02-22T16:26:14.768-06:002018-02-22T16:26:14.768-06:00The convincing power of a conjecture, such as P ≠ ...The convincing power of a conjecture, such as P ≠ NP, also depends on how convincing are its equivalent reformulations. Consider the following conjecture: NPI (NP-intermediate) is non-empty. Since not a single natural problem has ever been _proven_ to fall in NPI, under the assumption that NPI is non-empty, therefore, it is not so hard to imagine that an unsuspecting person could easily "vote" for the claim that NPI is empty. However, it is known (by Ladner's Theorem) that the emptiness of NPI is _equivalent_ to P=NP.Andras Faragohttp://www.utdallas.edu/~farago/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36373863031295119032018-02-22T13:26:20.409-06:002018-02-22T13:26:20.409-06:00Since you've been in the business for a while,...Since you've been in the business for a while, did any of your beliefs changed over time? Would you have guessed before the NN revolution that TC0 = NC1?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com