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 nice …….keep it
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…
Here is the kind of paradigm shift that I had in mind:
Could we have NP!=P from a finitary perspective, and P=NP from a non-finitary perspective?
I argue (link below) in the case of Cantor’s Continuum problem that two such interpretations can be seemingly contradictory, yet complementary.
http://foundationalperspectives.wordpress.com/2013/09/05/the-answer-that-hilbert-never-envisaged-for-the-first-of-his-twenty-three-problems/
Regards
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)
Gentlemen,
What’s your take on this: http://arxiv.org/abs/1205.6658
Quite a claim, no?
Dear Professor Lipton
I have studied the problem P versus NP, since I was in the career of Computer Science. I know a professor who told me “Every expert in computer science have dreamed under the shower with the problem P versus NP” and I asked to myself: Why don’t I try? I graduated and continued studying in that problem. After various intents I found something very interesting: What happens if we build the inverse (backwards) of some deterministic and polynomial Turing machines? Then we will get some non-deterministic and polynomial Turing machines which have as input the output of the original deterministic Turing
machines. I continued researching in that way. Then I started with a version in ArXiv,but without any advisement and I made a lot of versions. One of the version which I didn’t upload to ArXiv I sent to IEEE Latin America Transactions in 2010. In August 17th of this year my paper “P versus UP” was published in IEEE and I wish to share with you my final conclusion:
“We can easily defined identity functions over some deterministic Turing machines which are one-to-one, string to string and polynomial with some arguments (or inputs) and in the rest of the arguments in which are not defined they could never halt in these deterministic Turing machines. Then, if P = UP and that means the impossibility of one-way functions, then it could be that the inverse of these functions may be polynomial and therefore the original function will be polynomial too. This event occur because the reverse of these deterministic Turing machine will be unambiguous Turing machines: if some input doesn’t reach the halting state in the original deterministic Turing machine, then this input won’t be accepted in the non-deterministic Turing machine which has as initial state the mentioned halting state. This result implies a contradiction, the reason is: if P = UP, then we could decide some undecidable language over a deterministic Turing machine which is an absurd (as Turing proved) and so, P is not equal to UP, the existence of strong one-way functions is a fact and P is different from NP.”
If you wish to revise it in detail, the links of the spanish version in IEEE and the english version in ArXiv under a pen name (Asia Furones) are in the address:
http://the-point-of-view-of-frank.blogspot.com/
I’d wish you read this comment. Although I have been accepted by IEEE-AL I need the opinion of the experts,
Thanks for your time.
The phrase “…if P = UP, then we could decide some undecidable language over a deterministic Turing machine which is an absurd (as Turing proved) and so…” is not correct because I used in my paper “P versus UP” in IEEE that we can’t decide if any deterministic Turing machine doesn’t halt in polynomial time, which is similar, but not the same. I usually makes common mistakes when I write in English, so I going to share a comment that I sent in a email to a friend in Spanish right now, which express my ideas about my paper. This will be my last comment in any blog about my proof, because I check this is a waste of time, so here is my comment:
“…Yo sigo apostando que mi argumento tiene su belleza y sencillez al mismo tiempo. Hasta ahora se habian virado las maquinas de Turing al reves para hacer salvas sobre la configuracion de una maquina de Turing (o programa). Pero nadie ha visto las implicaciones que eso tiene con el problema de parada de Turing. Veras si una maquina de Turing para con una entrada entonces es posible hacer ese proceso de corrida a la inversa desde el estado de parada hasta el estado inicial obteniendo la misma entrada dado la salida. Por lo que en muchas ocasiones las maquinas de Turing inversas seran maquinas de Turing no deterministas polinomiales, que deciden algunas maquinas de Turing deterministas que no paran con algunas entradas y con otras entradas si lo hacen en tiempo polinomial. Por supuesto estas maquinas de Turing no deterministas pueden ser llevadas a deterministas pero seran exponenciales. El hecho es que el estado inicial de la maquina inversa va ser el estado de parada de la original por lo que en muchas ocasiones se puede garantizar que se puede aceptar o rechazar en tiempo polinomial las entradas de la maquina de Turing determinista original sobre una no determinista. Se puede apreciar usando los mismos argumentos de Turing (en el problema de parada) que es imposible determinar en tiempo polinomial si una maquina de Turing determinista no para con alguna entrada, pero si se podra en muchas ocasiones con una maquina de Turing no determinista. En fin: “Cuando un niño nace, no se puede esconder”…”
Good Luck.
Hi,
I have some problems on reading your comments. Sorry! I can read Portuguese, English and Spanish, but I really believe that some of your posts can deceive us from the objective of Professor Lipton Blog. I wrote my own proof P=NP, it is in my page and I frequently update that in order to make all statements clear but, frankly, such a big task is to be performed alone and carefully. I cannot take time of referrers until I am 100% sure I wrote one good version anyone can read and benefit from that. What is more, I intend to turn part of the proof I wrote into a paper, so, I can, if I am correct, build the steps to make all my statements crystal clear. I must make my point clear. I cannot by some dictatorial act obligate the reader to read my proofs if I am not sure that this is the last and final (very clear) version.
I believe that one has to be clear and we, the P=NP-searches (nice name, I think!) cannot make strong claims like: “Ready my paper, learn Spanish and say I am right!”. I do not know about the other members of Professor Lipton blog, but I believe there are clever ways to show you are right besides your posts.
I keep posting updates in my page and, hopefully, my idea will be accessible to anyone but me. Meanwhile, I am writing papers (in English, with my so charming accent!) so that people can see my point.
Last point: “Professor Lipton, read my paper or I kill you or I kill myself!”! OOOPPPSSS Kidding!
best
angela
—
Dr M. Angela Weiss
http://www.ime.usp.br/~weiss/
Departamento de Matematica
Instituto de Matematica e Estatistica – USP
Caixa Postal 66.281
05314-970 Sao Paulo, SP Brazil
The bird fights its way out of the egg. The egg is the world. Who would be born must destroy a world. The bird flies to God. That God’s name is Abraxas.
Herman Hesse
3SAT == Quantum Blackbody Radiation
Hello,
I’m writing to let you know that your blog has been selected for inclusion
in our list of the Top 25 Computer Science Blogs of 2012. Blogs were
selected based on the frequency and quality of posts over the course of
last year, as well as their usefulness to current and aspiring computer
scientists. You can view the entire list at
http://www.topcomputersciencedegrees.com/best-computer-science-blogs-of-2012/.
Congratulations!
J. Shane
Managing Editor
TopComputerScienceDegrees.com
editor@topcomputersciencedegrees.com
Oh, and let this electronic Cross-Product’d Electronic Tomahawk Chop ensure that my transmission is not filtered in any SPAM Domain.
It’s nice to see a blog on Computer Science theory rather than programming. The level of reader engagement gives me hope for the future of the study over the objections of those who believe universities should stick to training students for jobs in engineering. Keep up the good work, professors Dick and Ken!
Dear Prof Lipton and Prof Regan,
I am a fan of your blog both in maths and in chess where i am only an amateur and cannot confess to understanding everything on the blog. I am also a hemlock Holmes fan and in the current Elementary Season 2, Ep 2 is about Holmes and Watson (who is a woman in this US series) investigating the death of mathematician who was working on a proof t a puzzle in maths/comp sc called “P vs NP”. Here is a link to IMDB’s guide to the episode: http://www.imdb.com/title/tt3125780/synopsis?ref_=tt_ov_pl
Is this the same as the famous P=NP on this blog? I would like to read your expert commentary on the episode and its representation of the maths and mathematicians.
Most universal statements about algorithms aren’t recursively falsifiable. That is, you can’t design a program that looks for a counterexample. This distinctive feature makes the conjectures in complexity theory quite different from those in arithmetic. The philosopher Karl Popper believed that a hypothesis had to be falsifiable in order to belong to Science. That is, you must be able to conceive an experiment which might disprove it. Therefore, an assertion such as P!=NP shouldn’t be regarded as completely scientific – even though it’s perfectly rigorously stated.
Hi Serge.
Do you still believe that P! = NP has some physical constraint?
Our next post may address this…
Hi Fabio,
That is one possibility, indeed. We might find ourselves to be in the same situation as Euclid and his successors, trying to prove the fifth postulate before Einstein came along and said “Hey, it all depends on the curvature of your space!”
There’s also the possibility that complexity’s only the other face of undecidability. It seems to be the case that, whenever a problem in NP is not in P, you can’t prove that it isn’t. So, whenever you try to break an encryption system, you’re facing the same problem as the mathematicians who want to prove that it’s secure. Rather puzzling… 🙂
Fantastic, Professor Regan!
I am looking forward to seeing this new topic here.
Hi Serge,
Let me see if I understood what you mean.
Let’s suppose based on your assertion:
“So, whenever you try to break an encryption system, you’re facing the same problem as the mathematicians who want to prove that it’s secure”
Hypothetically speaking, this means that my goal would be to prove that such a encryption system is non-one-way, and mathematicians’ goal would be to prove that such encryption system is one-way.
If we all fail, one can directly deduce that such a encryption system exhibits a dual nature, though this conclusion seems absurd!
Ok?
Hi Fabio,
Our encryption system’s certainly either one-way or non-on-way, but not both. I we all fail to know, that’s probably because the matter is undecidable. I suspect there’s a zone of undecidability that prevents all from knowing if this encryption system is breakable. So much so that, whether P=NP or P!=NP, the result is the same: you can’t break the system but nobody can prove it.
If we believe P=NP, we’ll say that the system is protected by the undecidability of this conjecture. If we believe P!=NP, we’ll have the choice: the system is secure either because it’s one-way or because its non-one-way-ness is unprovable. That’s why I speak of a non-scientific fact, quasi-religious. Whatever you believe about it, the practical consequences are the same.
Serge,
your reasoning is correct, but there is a underlying detail in your own reasoning you did not notice. You advocate if “P=NP or P!=NP, the result is the same”. I also believe it, but your inference exactly occurs because the matter is dual-natured. If the matter is undecidable is because we cannot decide between “yes” or “no”, and if this occurs is because “yes” and “no” exist at once. This rather condition features a one-way function.
There is an interesting work about the possible existence of a non-invertible mapping that paradoxally is invertible as well.
(http://arxiv.org/abs/cs/0010011).
See, albeit such a condition seems quasi-religious, it is certainly scientific. Well, at least scientific fiction!
In a recent work, Leonard Mlodinow (co-author with Stephen Hawking in last edition of “A Brief History of Time” and also Star Trek’s screenwriter) released a preprint (http://arxiv.org/abs/1310.1095) wherein it is argued that Bennett’s mapping of Maxwell’s demon (a thermodynamic version of Turing machine) exhibits an arrow of time, albeit it is completely invertible.
Another quite recent preprint (http://vixra.org/abs/1311.0135) demonstrates this particular condition based on entropy increase: Bennett’s mapping violates second law of thermodynamics when runs backwards.
This means that Maxwell’s demon, while it is invertible because restores the memory’s neutral state at end of process, it is non-invertible because does not run backwards!!! If this one-way condition exist, then no natural proof method can distinguish between P and NP, as Razborov and Rudich defined.
Wow, how brilliant! Just let me the time to digest… 🙂 My own view may be summarized more simply: the PvsNP problem is the punishment we get for modeling computer science into Peano arithmetic.
In quantum mechanics, you have the probability waves that determine the likeliness of observing a quantum particle. Similarly in computer science, there’s Kolmogorov complexity that rules the probability for a processor to output a particular sequence of bits. When you know that current research makes quantum mechanics the basis of computing, this analogy’s certainly more than a coincidence.
I think the traditional notion of existence yields too much undecidability when it’s applied to algorithms. For this reason, it might be usefully traded for the notion of probability. Some algorithms are more likely to be found than others. End of the story.
Ok, Serge.
Thank you
As an undergraduate mathematics student I don´t understand the question…
So every non-deterministic turing machine can solve a given NP problem within polynomial-time and every deterministic turing machine can check the solution within polynomial-time, right?
Here is my question: Why can´t you computer scientists create out of the solution of the non-deterministic turing machine an algorithm for the given specific problem, which can run on a deterministic turing machine within polynomial-time?
Shouldn´t it be P=NP, because you can create a “trivial” algorithm, if you have the solution beforehand?
Can someone explain? (I don´t want to ask my prof, because I´m afraid that he might think that I lost some screws and I suspect that many other people made my mistake before me.)
I think understood my mistake. No need to publish anymore.
Thanks for your contributions to clearer thinking.
Hi ,
P=NP . Quantum computing using (ie) split photons where one half A , can reveal information about half B , no matter where in space and time in the universe B exists.
A way to show a proof is calculate the next say 100 lotto drawn winning combinations.
Is it possible the P can equal NP sometimes as opposed to everytime?
@Aleksey Old comment, but I stumbled across this blog and saw this was unanswered. To my understanding, many instances of specific classes of problems in NP ARE solvable in polynomial time. Many times it’s a minority of specific cases that don’t seem to admit a polynomial time algorithm.
P=NP is mathematically equivalent to the Halting Problem, the Uncertainty Principle, and Godel’s Incompleteness. Can we please just stop wasting time here? It’s been like at least 100 years already.
Sorry for my “english”. Estoy intentando comprender el problema P vs NP con los muchos recursos disponibles en la red. Si no entiendo mal,un solo contraejemplo de un problema NP que no esté en P sería suficiente .Ha habido intentos de buscar o incluso diseñar ese contraejemplo?Tenemos alguna pista o intuición de como debería ser?Pregunta tonta,hablamos de problemas que tienen solución,no?si son indecibles,sin solución o con infinitas soluciones, están fuera de este problema?. Gracias
I was wondering if you could possibly inspect/”peer”-read the following argumentation-try of mine:
https://twitter.com/koitiluv1842/status/1491747909607383042
This is the original of the afore-mentioned proof:
https://www.researchgate.net/publication/351475502_A_polynomial_time_algorithm_for_3SAT_the_newest_version_of_May_2021
One branch of my Esst (= expressions-systems satisfaction theories) to realize P-time solutions of NP problems:
https://twitter.com/koitiluv1842/status/1507325261934923777
I was wondering if you all could inspect/check_out this person’s claim that the 3SAT problems can be solved within polynomial time periods, please?:
https://twitter.com/danluu/status/1417215848633159689
Dear friends! https://www.researchgate.net/publication/367077736_THE_THEORY_OF_PLAFALES_P_VS_NP_PROBLEM_SOLUTION_SECTIONS_1-7 Soon the full version will be done.
In June 2023 I am coming with a paper P = NP. I prove this by giving a deterministic algorithm that solves any 3SAT instance in O(n^7). Watch for it. This is a promise.
P=NP simply/directly means the inevitabilities of the breaking of all the secret codes, of crazy psychopathic hackers’ hacking into and hijacking of nuclear missile silos, and of a global nuclear war depicted in this movie:
Proofs of the break-abilities of all the (post-)RSA secret codes:
https://twitter.com/koitiluv1842/status/1413648310703853568
Is this valid, I wonder?:
https://www.academia.edu/51021251/From_the_Proof_of_the_Four_Color_Theorem_to_P_NP
The above author’s conclusion:
3SAT ⇔ planar 3-color-ability. Plus, they both have P=NP-time solutions.
Please, check for errors my proof of P=NP:
https://drive.google.com/file/d/16Ws_eZF8f-rn1mFvkIT-UdMdvTwOu4vO/view?usp=drive_link
Checking it may require logic expertise.
Send your proof verification result to porton@narod.ru