About P=NP and SAT
This is a blog on 
I plan to make the posts people oriented, I will talk about the “who” as much as the “what.” Since I have over 30 years of experience working on this problem, I know almost everyone that I will write about. I think this will make the discussions more interesting, and I hope that you will agree. However, my real reason for making “who” central is to explain what researchers do when they work on hard open problems. They make mistakes, they go down dead-ends, they make progress. Also students may not know, but even experts sometimes forget, that ideas that we now see as easy were once unknown.
I love your site. Keep it up !
Very great website! I have enjoyed reading it over the last month or so. I have a hypothetical question for you: Assuming someone had a polynomial time algorithm to solve 3SAT, how would that person go about getting the Boolean formulas in 3-CNF of the remaining millennium prize problems? Has someone already done that work, or would the formula have to be created from scratch?
Best,
Mark
I believe that they would have to done from scratch. But the formulas, I believe, would only be able to encode: is there a proof of the RH, say, in this formal theory of length L. Since even if RH had a formal proof in that theory, L is likely to be huge. So the folk claim that SAT would get all the Prizes is a bit unrealistic.
Note, for a problem like RH there might be a way to show that SAT could help check for bad zeroes. But even that I believe would lead to huge SAT formulas.
I think you are right. A conjecture might be easy to solve that way, but Yang-Mills I think would be impossible. It would be almost as difficult to find the Boolean formula that would solve the rest of the problems as it would to just sit down and think them through.
I do believe, however, that the answers are related, and that if you can solve P vs NP, you are more likely to figure out a solution to the others.
Another question for you, since you are not at all unfamiliar with this problem, I’m sure you’ve been thinking about the consequences of such an algorithm if it were true. What advice would you give to an unknown, unschooled in math and comp sci, young, never published person who might have a working 3SAT algorithm who fears the establishment will just think, “another proof that P=NP by an unknown… rejection, I don’t even have to read this.” Also, do you have any journals or editors to recommend this person?
Well, first, I think that the guy that boasts: “Look, I just solved the question whether P=NP. I will claim my prize tomorrow!” is to naive because this problem, I believe, has a very simple answer but we have not grasped the entire issues. Besides, a polynomial algorithm for 3-SAT can be a HUGE polynomial machine.
I wrote a simple polynomial algorithm for 3-SAT. I have it being polished for one year and, I believe, I very much made it more simple to be grasped. I really believe that, it will became an useful contribution. It is posted in
http://www.ime.usp.br/~weiss
Anyway, I share the ideas: the answer is quite simple. We have not grasped the whole idea and main definitions are being missed. Even so, how huge can an algorithm be?
best
angela
Hi Angela, I looked a bit at your paper, and two or three major concerns come to mind about the algorithm you propose. While the factoring aspect is interesting and novel, my first initial concern is that it requires repeated, iterative search, which… should be relatively minimal if it exists in the algorithm at all. The words “We repeat the procedure,” while is not a counter proof in and of itself, it indicates that the algorithm is not polynomial. However, I actually believe you DO have a polynomial algorithm for 3-SAT, except, it is unfortunately, not deterministic. In fact, your algorithm will work in MOST cases, but will unfortunately produce FALSE NEGATIVES due to how you determine “Necessarily False”. There can not be a “necessarily false” procedure the way you indicate, as there are other ways in NP# to produce certificates that would use your false literals in ways that are true. The means, in very high backbone 3-SAT instances, you will find an output error at least some of the time. Low backbone 3-SAT problems will likely produce certificates unless the formula is not satisfiable. My final concern is that in the clauses which do not have factorable literals, to make these two sat, you need to expand the number of clauses and add the appropriate literals, thus making the formula larger. Say a backtracking algorithm was put on this 2-SAT formula, it could be pseudo-polynomial at best, which is still an improvement on current work, and worth checking. So perhaps not all effort is to waste?
Dear Mark,
Thank a lot for your feedback. It was useful! I am not that concerned with all that partition issue. Partition stops and it is well determined when it stops. I can show that a 3-SAT formula PSI is satisfiable iff any of its partitioned version is satisfiable as well. we, we repeat the algorithm until obtain a 2-SAT formula. It is a search on a decreasing set, say, in the worse case of sizes, N,N-1,,…2,1. That is, O(N^{2}. In order to avoid long replies and unnecessary arguing about a not so solid ground, I’ve posted in my webpage examples of factorization.
More, on my discussion group.
Thanks a lot, again,
angela
I have exactly the same questions. Only that I’ve worked on the topic for many years, have a Ph.D. in math and partially know the answer.
Can it be that a resolution of the PvNP problem merely awaits a paradigm shift in the way the problem is viewed!
I have the impression that P = NP and that won’t require such fancy things like paradigm shifts and so on. Well, paradigm shifts might happen and solve it, but I think a solution exists and is simpler.
One thing that I’ve noticed, current NP-complete problems are too “dirty”, in the sense that they put among the conditions much more than necessary. Problems would remain NP-complete even in very much simpler form, even assuming more on the problem.
While there’s no need to render the list of NP-complete problems any longer beyond the current 3000++ list, we do need GOOD NP-complete problems, which should arise from the known ones, with further elaboration.
ILIA , I fully agree!
Counting the perfect matchings is one such clean (although NP-hard) problem.
It is amazing that people who believe/claim NP != P think they have taken the full control over the “theory” of combinarotics.
In one of the Harary’s books on Graph Theory I once read that some graph theory results have often surprised even great mathematicians.
Yes, IMHO the PvNP problem is awaiting a least two paradigm shifts.
Firstly, it needs a shift in math in order to show that it’s undecidable. Why not try to devise a neat axiomatization of the complexity classes, independent of any computing model such as Turing machines and the problems they can solve? When Cantor was trying to prove the continuum hypothesis, he wasn’t aware that his set theory badly needed an exhaustive list of axioms. It could well be that we’re in the same situation as Cantor was in before Zermelo and his successors turned up. I’m pretty sure it would have been difficult to convince him of a lack of rigor in his set theory, just like most of us today about the complexity classes of solvable problems.
Secondly, it needs a shift in physics in order to prove that NP-complete problems can’t be solved quickly in the world of real computers running on electricity. Complexity theory hardly ever mentions energy. Only is the entropy of the data discussed sometimes, in the disguise of Kolmogorov complexity. What if computer data possessed also a mass? Then the whole of relativity theory could apply to them…
I think it’s just euphoric to say that P = NP would solve all the remaining Millennium Prize problems. What could be done today is to prepare those problems. Suppose that P = NP. Here is how would you prove or disprove this conjecture. Obviously the assumption would not suffice because there would be the amount of work to be done that one can do having a constructive proof of P = NP. Nonetheless I have seen none of these conjectures reduced to mere amount of calculations that we know how to do and are too much to do. That would be interesting.
At the risk of sounding like a complete newb, I want to point out that your site seems to be missing a readily available definition of SAT as you’re using it here.
I just wanted to mention it before I go elsewhere to find out; I’d moseyed to this page, entitled “About P=NP and SAT”, hoping it would’ve answered the question, but I suppose that “even experts sometimes forget that ideas that [you] now see as easy were once unknown.”
Qrystal,
No my error.
SAT is the class of boolean assignment problems. Given a set of clauses the task is to assign 0,1 to the variables to make all the clauses true. A clause looks like
x or y or (not z) and so no. This is one of the first NP-complete problems. See here for details. I hope this helps.
I find your blog very refreshing. Thank You!!
Some comments:
1) There has been considerable progress in building general practical SAT solvers (Today’s solvers can handle upwards of 10 million clauses with millions of variables obtained from real-world apps). However, there doesn’t seem to be as much interaction between theoreticians and practitioners as one would like.
2) It would be great if you could add some discussion on “Independence results for the P vs. NP problem”. There is a paper by Scott Aaronson that is a good starting point on this topic.
I think that it is somewhat of an exaggeration to write that Gödel’s 1956 letter was written “decades” before Cook and Karp’s 1971 formulation of the P-versus-NP problem. By my calculation, there is only a 15 year span that separates the two events.
Dear Professor Lipton and all bloggers,
I’ve recently posted a paper in my page.The paper, “A Polynomial Algorithm for 3-Sat” is on my webpage,
http://www.ime.usp.br/~weiss
and I wait for criticism.
Thanks!
angela
Usually people who try to discover the famous P versus NP problem say “I have solved it”. For me, personally, it seems a bit pretentious to announce such discovery as a fact. I also think it will be difficult for a non-expert in the subject to solve it; this possibility would be like the probability of one in a million. Since 6 years ago I spent my time trying to solve this problem as a hobby and I have found that the model of Turing machines is a great tool to demonstrate that result. I also think, that a trivial way to prove a result in this field is proving that the language sets P and NP are disjoint, demonstrating that there is a problem in NP that is not in P. I upload to Arxiv the version number 11 which although it maybe have trivial mistakes, such as lack of proficiency in English, still remain me convinced since a few months ago. I want someone to refute my arguments, but I am just a lover of the subject outside the academic circuit, I have no one does. Please help me, here is the address:
http://arxiv.org/abs/1011.2730
(Version 11)
When i said ” the language sets P and NP are disjoint” i actually want to say ” the language sets P and NP are different” which is no the same. My native language is not the English and i made a mistake on writing that comment.
I will put a fragment of my abstract for avoid being misunderstood again:
<>
Waiting for criticism, like they say…
Fragment:
The existence of a language in NP, proven not to belong to P, is sufficient evidence to establish the separation of P from NP. If a language is not recursive, it can’t belong to the complexity class NP. We find a problem in NP which is not in P; because if it would be present in that class, then it will imply that some undecidable problem will be in NP too. That’s why it can be confirmed by reduction ad absurdum the following result: P doesn’t equal NP
Your entire premise is just not true, Frank, no matter what your native language is. First of all, you make no distinction between NP-Complete and NP-hard. You then “prove” an NP-hard language you call “C” is not in P, but C seems like it might be an EXPSPACE-complete language (based on the fact you keep adding tapes to the Turing machine you define), which we already know doesn’t include P, but is still NP-hard. So you’re proving nothing about the nature of NP at all.
The problem with your statement:
“The existence of a language in NP, proven not to belong to P, is sufficient evidence to establish the separation of P from NP.”
is that you are confusing your existential and universal quantifiers on languages in NP. It should read: “If ALL languages in NP are proven not to belong in P, this is sufficient evidence to establish the separation of P from NP.”
Also, you are using proof by contradiction (reduction ad absurdum) to prove something is not true?? I could be wrong or misguided about this, but isn’t proof by contradiction only used to prove true statements? Frank, the issue is not with your difficulty with English, it is with your use of logic.
jmarkinman:
The sentence “The existence of a language in NP, proven not to belong to P, is sufficient evidence to establish the separation of P from NP.” is actually quite true. You just need one counterexample. Of course this may not save the rest of the proof.
Here is why you are wrong: P<=NP; P<=EXPSPACE; NP<=EXPSPACE; EXPSPACE!=P does not imply P!=NP. QED
Johansen i have sent emails for many people and nobody answer me yet. Oded Goldreich said “As such, they also attract the attention of non-experts, and one annoying consequence is a flood of false claims of resolutions of these problems…” and also said “Furthermore, I believe that in such a case, the successful non-expert will be able to convince the scientific community that his/her claim is indeed valid…”. The only thing that Oded don’t know is: how the poor people (who can’t go to the events) and unknown (who researches answers him in other words: “I dont’ have the time to waste it with you”) can break this “wall of refusal”?
I guess nobody knows. I would wish have the reason, however i actually known that the probability of being right is very few. I only asking for a refutation (a serious refutation).
Could you?
Good luck.
Frank, the problem with your argument is the same problem with Vinay’s solution, it is not sufficient to prove P!=NP by showing there does not currently exist an algorithm to solve an np complete problem in p. You must provide all algorithms that do not exist to do so which is an impossibility. On the other hand, it on,y takes one algorithm in p to solve an np complete problem to prove p=np. i suggest trying to find a lower bound over boolean circuits before declaring the solution if you really believe P!=np. however i think p=np since i have found an exception to cantor’s theorum which directly implies p=pspace.
Mark Inman. I think that is a waste of time discuss this issue like a matter of who have the reason. I think that the best thing that we need is being revised by another person who have the sufficient knowledge to refute our intend. I just uploaded the version 13 of my paper in the same address the last week and no one give me any argument to improve my paper. Sometimes i feel a little dissapointed because even if we have a little reason of what we are saying, i feel that we will never be heard by no one and I think that this feeling is terrible. The true is that: nobody believe in amateur, even though the academics spent their time in blogs arguing if some of them can do something. Good luck Mark, if you can.
Your statement in your abstract: “The existence of a language in NP,
proven not to belong to P, is sufficient evidence to establish the
separation of P from NP” is just NOT true and then your entire argument hinges on this fact. To improve your paper, you should try to prove an exponential lower bound over increasing Boolean circuits for an NP-complete language. But I am already quite sure P=NP: http://www.scribd.com/doc/61288772/The-Art-of-Infinite-Reckoning
The PvNP problem lies at the intersection of physics and mathematics.
Factoring is equivalent to breaking a composite number into prime parts – there’s a “multiplicative force” that maintains the prime pieces together, so that breaking a number apart requires a “computational force” of equal intensity. Similarly, the search for a Hamiltonian path in a given graph is a sort of extraction that requires a “computational force” equal to the “cohesive forces” that hide it from our knowledge.
When we’re able to give a precise meaning to these two kinds of force – the cohesive one and the computational one – then the PvNP problem will be solved. But I suspect we’ll have to take into account the fact that our brains are computers too… hence the probable undecidability of the whole thing.
I fixed some trivial mistake with the version 15 of my paper that an editor of a magazine of ACM suggested me. I’m still waiting that somebody refutes my arguments definetly. Nevertheless i’m really sure that maybe i could have trivial errors but the whole idea is in general correct. I’m looking for someone which have the sufficient knowledge to refute my arguments because i don’t have the assuredness whether that editor will continue with the revision. For anyone who love this subject i’m ensuring a good interchange and an interesting idea. See the version 15 in:
http://arxiv.org/abs/1011.2730
The editor continue with the revision, but his comments are in a long intervals of time, maybe because he doesn’t have much time to use in the revision. The fact is I’m still waiting that somebody can discover my flaw. If anyone find my fundamental mistake I will be very thankful, however I believe very deeply that such possibility doesn’t exist. Waiting for any comments and hoping a serious refutation of version 15:
http://arxiv.org/abs/1011.2730
Frank, in your Proposition 3.1, for any deterministic Turing Machin M of one single tape, another Turing machine M’ with 2-tapes can be built, which simulates M and M’ in Mca. If M never stops, how can you simulate M in M’ and ensure M’ halts with a result y in the second tape? Do you mean M’ can judge if M can stop or not, or M’ just forces M to stop if M runs too long?
Philips, thanks for your comment. With the construction which I did in Proposition 3.1 I only guarantee if M halts then M’ halts too and if M doesn’t then M’ neither. Because I assure with a sequence of steps that M’ halts only when M halts. Read once again and you will understand, however you can email me whenever you want, that I will answer you as soon as I can. Good Luck.
Here’s my current supposition about the P versus NP problem:
1) If P!=NP then there exists no proof of P!=NP – precisely because P!=NP.
2) If P=NP then there exists no proof of P=NP – precisely because P=NP.
In other terms, there might be an algorithmic principle of relativity: “It is not possible to make a distinction between a world where P!=NP and one where P=NP”. In this sense, our problem would appear to be much more ill-posed than undecidable.
This reduces the claim to metaphysics, which can be defined as something that by nature is unsolvable. I’m quite sure the problem of P vs. NP is well stated and is solvable. I think the problems we face in computer science go back to Cantor’s logic on higher orders of infinite sets and cardinality.
Maybe you’re right, I don’t know. However I enjoy the following analogy:
1) set X power set P(X)
2) problems computable in time X problems checkable in time X
When you know that even the existence of P(X) is independent of the other axioms of ZFC – as is the existence of a set of intermediate cardinality between those of X and P(X) – you may wonder why everything should have to be provable in the world of complexity classes.
… and by the way, I haven’t given up the idea of proving both 1) and 2) in my initial comment. If we could prove that both P!=NP and P=NP make their own proof impossible, then my principle of relativity would be a theorem.
It could even turn out to be the other way around: that P=NP in Peano Arithmethic but that the algorithm isn’t computable for a human brain, because of a yet unknown physical law that no device can solve an NP-complete problem in polynomial time.
So P=NP in mathematics, whereas P!=NP in physics: we’ve perhaps always been working in a mathematical framework that didn’t fit the physical reality, in very much the same way as Euclidean geometry didn’t fit General relativity.
To reach our goals, we must go into narrow ways. That is the most important thing I’ve learned in all these years trying to demonstrate P versus NP. The last Friday I thought I had found my fundamental mistake. I actually needed to do something, but then, I understood that I didn’t have a flaw: I only needed to search a string that was unique in relation with some input in any deterministic Turing machine. I asked to myself: How can I improve my paper changing only this detail and achieving in the same time that any graduate student in Computer Science can understand it?
Then, this last weekend an idea came into my mind and I remembered the question that Serge Ganachaud did about describing my result in a simple way and I tried to do it in the new version 19 of my paper taking into consideration this point. The result continues with the same arguments, because the paper hasn’t change at all, only some details that I believed that are not necessary. I believe any person like you: Serge, Philips and all the lovers of this problem, could understand it. Here is my outcome:
If we have the sequence of all states that visits the execution of a program in any deterministic Turing machine with some input, then there isn’t a polynomial algorithm which finds with that sequence and the Turing machine its respective input (considering that the sequence could contain any state many times).
The strong reasons of this statement I explain them in my paper, but as everybody could see: each state in a Turing machine could read many symbols, that´s why we must prove all the possibilities in most of the times.
http://arxiv.org/abs/1011.2730
See version 20…
http://arxiv.org/abs/1011.2730
I tried to make all this last versions in a simple way: 19, 20 and now 21. I think that I arrived in a point that my paper is trivially wrong or just correct in a way that everybody could understand. The editor who was doing a revision finished, because it became very difficult for him to understand me, that’s why I decided to do this three versions, improving few details in each one and making a simple description of my outcome, short and clear, for everybody.
I do this comment for the purpose that somebody tell me definetly what is my fundamental mistake because the revisor couldn’t. I’ll hope somebody, someday, reads these comments I said to himself, “Well, let me see why this person insist so much in his solution”, and told me at the end, “Frank, you have a flaw for these reasons…” or “Frank you may have reason in some details but you must improve in others…”. This is what I expect of all this.
Maybe all this comments don’t have the correct words or aren’t in a good way but I assure there is good intention behind all this: I’m just an amateur and as amateur I need a help.
Waiting it…
http://arxiv.org/abs/1011.2730
I decided to send the paper to a reviewed journal. Maybe this will be the only way in which I could be reviewed for someone, and in the worst case in the revision they will tell me what is my fundamental mistake. However if anybody want to suggest me something, I uploaded in arxiv the last Friday the last version 22 . In this version I deleted the uniqueness of the output in the Certified Turing Machine, that caused so much confusion to the editor of the ACM magazine. Jan if you read this comment, I want to tell you, sorry for all the waste of time on this unclearly detail. I also feel a little ashamed with the author of this blog, because I used my comments about my versions in arxiv, maybe in an abused way, sorry for that too. I still need help, but I guess this time at least I can wait for the journal revision.
http://arxiv.org/abs/1011.2730
YOUR LOGIC IS WRONG FRANK GO AWAY
P=NP has been solved using Energy Loop Theory (The Prime Equation)
Dear Professor Lipton
I wrote many of these comments in your blog because I was asking for help. It’s very difficult for me, find any help because nobody has time even for its own problems. After of making a lot of intents in Arxiv I tried in Febraury with a new one. But I committed a mistake trying to upload a new version there and they denied me the permissions. So I uploaded it in a blog. I made two versions with different arguments. The last one “P versus UP” have survived from Febraury until now with not a single bad comment in relation with its arguments. These arguments consist in the following statements:
Suppose we have some Turing machines that halt with some inputs in polynomial time and don’t halt with others. These machines simulate the identity function in the inputs in which they halt. I proved that many of these machines have an unambiguous Turing machine as its reverse. So going backward we could decide in many cases, rejecting the input in which they don’t halt. So if P = UP implies that we could decide many of those machines using some deterministic Turing machines that run in polynomial time. But is impossible that we could reject in polynomial time when a Turing machine doesn’t halt in polynomial time using a deterministic Turing machine.
That’s all. Any help from you or anybody else will be very thankful from me.
The address is:
http://the-point-of-view-of-frank.blogspot.com/
In “P versus UP”.
The best of the lucks.
has anyone tried to hash the computation trees, to simulate non-determinism? (as an approach to p=np)