tag:blogger.com,1999:blog-3722233.post108551370561612427..comments2024-10-13T03:59:13.788-05:00Comments on Computational Complexity: What if P = NP?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-39079877949096977232023-09-21T16:28:44.881-05:002023-09-21T16:28:44.881-05:00Even if P = NP, wouldn't most hard problems re...Even if P = NP, wouldn't most hard problems remain open due to their generalized versions not necessarily being in NP? Just because P = NP does not make generalized 3n+1 any more difficult.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84389625836786793732016-06-23T05:08:25.073-05:002016-06-23T05:08:25.073-05:00Suppose the salesman was blind. He had to walk at ...Suppose the salesman was blind. He had to walk at a random angle to find the cities. The edges that decompose the space of n, to find each vertex, also form a graph of intersecting points, which in turn form undirected edges. <br />It could be said that a solution that efficiently determines what angle the next edge is formed at to decompose the space, also forms a directed graph as a set of potential solutions.<br /><br /><br /><br />Also 1 / e is a good number, check out the secretary problem sometime.<br /><br />J. Foster Goodmannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24082414162894025572016-04-29T20:21:07.244-05:002016-04-29T20:21:07.244-05:00Hello, I have the proof for P=NP in the folowing S...Hello, I have the proof for P=NP in the folowing Scribd page: https://pt.scribd.com/doc/307232804/Solving-the-Traveling-Salesman-Problem-and-establishing-P-NPAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79952142307469249482013-11-21T03:35:35.386-06:002013-11-21T03:35:35.386-06:00Will quantum computers idea become irrelevant with...Will quantum computers idea become irrelevant with strong P=NP? What about the new Bitcon-mania? Will this go total lost, its a market cost billions this days...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81779496828298304682011-05-18T04:06:58.510-05:002011-05-18T04:06:58.510-05:00I believe that this proof is simple, and easy to u...I believe that this proof is simple, and easy to understand. If you don't understand computers, just read the comments at the bottom.<br /><br />http://www.mysqlperformanceblog.com/2011/05/17/using-sets-to-solve-difficult-decision-problems-the-subset-sum-problem/Justin Swanharthttps://www.blogger.com/profile/08193089637089861226noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89110612785519656392011-05-06T14:18:09.943-05:002011-05-06T14:18:09.943-05:00How can one check a proof of length $N$ in polynom...How can one check a proof of length $N$ in polynomial time in $N$? This is far from obvious to me, because each step of a proof can refer back to any of the prior conclusions of the proof, which makes checking rather complex.Thomashttps://www.blogger.com/profile/09051024382193588456noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1086076536345696272004-06-01T02:55:00.000-05:002004-06-01T02:55:00.000-05:00I'm curious...Devlin remarks that mathematics has ...I'm curious...Devlin remarks that mathematics has reached the stage where the leading problems are incomprehensible to the experts, but cannot these same problems be recast into other problems that are more digestable ala Fermat?<br /><br />RaphaelAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085659359404316292004-05-27T07:02:00.000-05:002004-05-27T07:02:00.000-05:00One commentor correctly notes that finding the sma...One commentor correctly notes that finding the smallest program consistent with some data is not computable. I meant to say the smallest program with some reasonable (like quadratic) running time or even better the smallest circuit consistent with the data. These we can find if P = NP.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085630334333880842004-05-26T22:58:00.000-05:002004-05-26T22:58:00.000-05:00Hi Mahdi... perhaps then we would see a new brand ...Hi Mahdi... perhaps then we would see a new brand of luddites if P=NP. I would rather like to live in Algorithmica, though. Technology can be used to liberate or to oppress... and *overall* it has so far lead us to liberation.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085611527321221322004-05-26T17:45:00.000-05:002004-05-26T17:45:00.000-05:00A seven million dollar award for showing "P \neq N...A seven million dollar award for showing "P \neq NP" is okay, and it makes sense that we would have an easier and more efficient life assuming P=NP. However, a person who happens to (constructively) prove P=NP is better to be somehow fined instead, for introducing a totally disappointing world where even creativity has lost its meaning by being automated!Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085608578701922032004-05-26T16:56:00.000-05:002004-05-26T16:56:00.000-05:00This comment has been removed by a blog administrator.Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085585689911034732004-05-26T10:34:00.000-05:002004-05-26T10:34:00.000-05:00Lance, this was a fun post. I've been thinking abo...Lance, this was a fun post. I've been thinking about writing a science-fiction fantasy story wherein one person, for reasons unknown, performs subconsciously as a SAT oracle. It was intended to be an analysis of the sort you and Devlin give, crossed with a satire of the "Humans are better than computers because we are nondeterministic" argument you hear now and then.<br /><br />However, I gave up because I couldn't get beyond really fuzzy ideas, and figured I needed to learn (still) more theory.<br /><br />But I have a question - isn't finding the smallest program to fit some data exactly equal to finding the Kolmogorov complexity of that data? And this problem is Uncomputable, so P=NP wouldn't help at all (in the general case). Are you making extra assumptions about what the data are, or am I missing something else? Is mathematical-theorem-data actually less general than data?<br /><br />(Also, are you aware that Blogger tells me that I cannot post anonymously and then permits me to do so?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085529525900470952004-05-25T18:58:00.000-05:002004-05-25T18:58:00.000-05:00Hi Lance, On a second look I see that you already ...Hi Lance, On a second look I see that you already noted most of what I wrote in my comment --BoazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085528949810063392004-05-25T18:49:00.000-05:002004-05-25T18:49:00.000-05:00Russell Impagliazzo described a world where P=NP
b...Russell Impagliazzo described a world where P=NP<br />by an efficient (e.g., linear-time) algorithm in http://www.cs.ucsd.edu/users/russell/average.ps<br /><br />One consequence of this is that also the polynomial hierarchy collapses to P. This means that we should be able to solve questions like: "given this list of papers of Erdos, what is the smallest circuit that produced this list". Then, we could probably be able to predict the next paper on the list using this circuit. This of course works for books, paintings, movies, etc.. (Finding out the "blockbuster" formula for movies is certainly worth more than few millions)<br /><br />--Boaz BarakAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085528571859785512004-05-25T18:42:00.000-05:002004-05-25T18:42:00.000-05:00Hi Lance,
most of these claims (if P = NP?) are, ...Hi Lance,<br /><br />most of these claims (if P = NP?) are, I think, not necessarily<br />valid because, even though there is a polynomial-time algo for<br />SAT, it may be of order n^1000 - how can we consider such an algorithm ``efficient'' or ``acceptable''? But, I guess we want<br />to show that SAT is intractable by showing that P \neq NP.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1085525224249572412004-05-25T17:47:00.000-05:002004-05-25T17:47:00.000-05:00How would a strong P=NP generate proofs for theore...How would a strong P=NP generate proofs for theorems <100 pages? Wouldn't we still have to iterate through all of them and verify? From a given mathematical expression, how could strong P=NP be used to prove it?<br /><br />(Alas, if only we had such techniques now, we could get a resolution to the P=NP problem ;-)Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.com