Code It Up
So you think you have a proof that P=NP
|
| Randi 2014 documentary source |
James Randi is a magician who has challenged paranormal claims of all kinds.
Today Ken and I want to make a suggestion to those who claim they have proved P=NP.
No the claim to have a proof that P=NP is not a paranormal claim. But such claims are related to Randi—or the Amazing Randi as he is called. We talked about him before here.
Randi once helped run a contest to see who could find gold with their dowsing rod. He explained why he doubted one contestant:
If they really could find gold, why were they dressed so poorly, and why were they so interested in winning the prize?
I have the same question about those who claim that they have a proof that P=NP. Usually the proof is constructive and I agree with Randi:
If they really could solve P=NP, why
You get the idea.
Ken adds the obvious remark that if a foreign power or intelligence agency discovered P=NP, or factoring in P, they would still keep the lean-and-hungry look. But they are not the kind we are addressing here.
Coding Helps
Let’s look at a claims that P=NP is resolved. Yes, such a result is unlikely—many would say impossible. But we do get claims like this:
The following
is known to be a NP-complete problem; the following
is known to be a polynomial time problem. I can reduce
Usually the reduction is the reason their proof fails. Their claims about 
The reduction is often complicated, often poorly defined, often defined by example. Giving a precise definition for the reduction is critical. This is the reason we suggest the following:
Write the reduction down in code.
Even better, write it as a program in a real language such as Python.
There are two advantages in doing this.
- Writing it as a program in a real language will likely force one to define it precisely.
- Writing it down will also allow one to run the program on examples.
The later point is the key point. Even trying your method on tiny examples is useful. Even better if you can say the following we might read the proof:
I have tried my code on the following public set of difficult SAT problems. The code solved all in less than three minutes each.
This claim would greatly improve the likelihood that people might take your claims seriously. That your code worked correctly, forgetting the running time, would improve confidence. Greatly.
The Animal Farm View
Ken worries that some NP-complete problems are more equal than others. That is some problems, even though they are NP-complete may require reductions that blow up when encoding SAT.
We wrote about this before regarding the “Power Index” idea of Richard Stearns and Harry Hunt III. In their paper they gave evidence that the reductions from SAT to many familiar NP-complete problems must expand the size of instances quadratically, insofar as those problems have power index 
Ken ponders a related issue. Even problems with power index 
Anyone citing algorithmic success as evidence toward a claim of P=NP must compete with the real-world success of algorithms that do not represent claims of P=NP.
We have several times discussed the practical success of SAT-solvers on myriad real-world instances.
This situation has become real in the argument over achieving quantum supremacy. One who claims that quantum is superior to classic must worry that that classical algorithms can improve without making P=NP. A headline example from last year was when Ewin Tang—as a high-school senior—found a classical way to remove a plausible quantum advantage in a matrix-completion problem that underlies recommender systems. There are many “industrial strength” examples in this argument—see this May 2019 story for a start.
But…
Ken’s insightful comments aside, the key point is still:
Coding up your claimed algorithm for that NP-complete problem will still enhance belief.
This will happen even if the algorithm only succeeds on tiny examples. Indeed, if you cannot do this then I suggest that you will have an impossible time getting anyone to listen.
Open Problems
How useful is this advice for the vast majority of us who are not claiming P=NP or the opposite?
But….
What if the algorithms are shown as a pseudocode in a claim paper?
And…
What if the algorithms are so easy to follow that even a undergraduate student could understand them in a claim paper?
And…
What if the algorithms could be programmed even by a teenage maybe in Python after reading a claim paper?
Then…
What if that claim paper is this one?
https://www.preprints.org/manuscript/201908.0037/v1
Thank you Professors,
Your pieces of advice are always useful!!!
Sounds like a challenge! We await your github link with the source code.
Sure!!! Why not? I will start today on GitHub with a project of Scala. I will share the link when I finish.
Accepted the challenge!!! Here is the github link with the reduction:
https://github.com/frankvegadelgado/VerifyReduction
The proof of Theorem 9 in the paper of Frank Vega is wrong: a reduction does never keep the actual truth assignments of variables. For example if {x,y,z} are all set to True in a MONOTONE NAE 3SAT instance (which hence is not satisfied at least for this setting of variables), it is still possible to set {x, y, d_ci} to True and {z, d_ai, d_bi} to False in the corresponding MINXOR2SAT instance. And this setting leads to only one unsatisfied clause in the corresponding MINXOR2SAT P_i.
Dear Pepi:
Many thanks. My question to Frank is: Would tests of the code discovered this issue?
Best
Dick
@pepi People read these efforts. I am impressed by the dedication of the community.
Thanks Pepi,
When we:
“set {x, y, d_ci} to True and {z, d_ai, d_bi} to False”
then the statement that you proposed:
“{x,y,z} are all set to True”
Is actually not true because you set {x,y} to True and {z} to False.
Everybody that reads your comment is able to detect your error: It is not necessary to read the paper for the detection of your mistake. Sorry, I cannot fix something that is not in the paper.
Best,
Frank
Dear Professor and Pepi,
Pepi, you could email me whenever you want, asking question, doubts or finding possible flaws are welcome at anytime by email. Professor Lipton, an assertion in Scala is a pre-condition that should be validated in the instance. Every property of the instances is validated by the assertions when you run the unit test. Unfortunately, not all the proof can be covered by Boolean assertions in Scala. Therefore, I invite you to read the paper and check each Theorem with a reduction in the code into the GitHub project (you could find the right Theorem on Scala comments). The paper is not too long, either the code in GitHub project, so you might find whether the paper is correct or not in few minutes according to your experience in this field. Do not hesitate to do it and if you have any question, share it or simply email me, please.
Thanks in advance,
Frank
I am sorry, my argument was wrong, the Theorem 9 actually holds.
@pepi, it is worthier to recognize your errors, than being right in some issue. You showed you are very honest and brave with your comments: Congrats!!! However, this does not mean my proof should be correct in all the Theorems: Do not hesitate to contact me if you see something else that I could fix it.
Thanks in advance,
Frank
Can I ask you for one simple question? Suppose there exist certain problem which is known to be in EXP, one can try to reduce the complexity of the problem changing the conditions of the output needed to get NP-complete problem from a given problem. So, if suddenly EXP problems become easier, what is the influence of the certificate? And about your paper, what your problems(ESC-2 and KEC-2) exploit in structural nature of MIN⊕2SAT and your version of 3SAT? Can you clarify it in the introduction section of your paper?
First, it depends of the length of the certificate. If the certificate is not polynomially bounded by the input length, then this is clear evidence the problem is in NEXP or even a more difficult complexity class. Second, if the problem is EXP-complete and the given output belongs to NP-complete when the certificate is polynomially bounded by the input element, then this is clue that P is not equal to NP because we already know that P is not equal to EXP by the Heriarchy Theorem: Try to find the proof by yourself(HINT:Assume P=NP and find a contradiction). However, the results of the paper follow the other direction: I mean this might be used to show P=NP. I don’t understand the second question and what is exactly the idea I should put in the Introduction to make it better? Could you be more explicit, please? You could email me whenever you want :D. Thanks.
Dear vegafrank:
I think you miss the point. You need to code the reduction. If you have pseudo code already then should be easy. After all you are claiming one of the great results of…
I stand by my thought. Code it up.
Best
Dick
Dear Professor,
I will start a project on GitHub today. I think I can finish today since it is easy to transform the pseudocode to Scala or Java.
As you suggest, maybe I could find a flaw or an improvement while I’m coding.
Thank you for your advice.
Dear Professor,
Here is the reduction of the work including the unit test. It took some hours of coding to finish the reduction algorithms.
https://github.com/frankvegadelgado/VerifyReduction
All the best,
Frank
You completed the first step, now take the next one.
Use your reduction to efficiently solve SAT problems that currently cannot be solved in any reasonable amount of time.
Why not solve for the secret key of a large bitcoin wallet and profit?
Or, if you don’t feel like making your own SAT problems, enter the next SAT solving competition — http://www.satcompetition.org
Dear Peng,
Our reduction consists given an instance of an NP-complete problem and its certificate, then we output an element of another language in the class L. It is not a common reduction, but a verifier with output string in its tapes using a halting state instead of the acceptance or reject state. We assume the existence of such verifier is an evidence of P=NP, because we use a logspace verifier which is based the class NL and NL is a subset of P.
Thanks
Important: The assumption of P=NP is not in the paper. We only explain this interesting “reduction” verifier in the paper and in the code in github we implement the verifier algorithm in Scala. Note, it has no sense to solve a SAT instance if we have already its certificate. This has only sense for a verifier.
I have a psychology question: Are we humans wired to believe that P=NP? It seems to me that we are. Intellectually, I know that P is not NP (I even wrote a paper claiming to have a proof), but I cannot help feeling in my heart that they are equal. If a problem has polynomial size and its solution can be verified in polynomial time, shouldn’t it naturally follow that it can be solved in polynomial time? My intuition tells me yes, but my intellect tells me no.
The fact that so many people claim to have proven P=NP and so many people claim to have proven they are not equal confirms to me that there is a split between the intellect and intuition with regard to this problem.
The answer is clear. People are not wired biologically to believe such extremely abstract ideas. Why wouldn’t you think that P can equal to NP in the finite case and not equal in the infinite case? The idea looks silly at the beginning, but if you can show that lower bounds can be lowered by restricting the maximum size of a problem you can get away with way lower bound than currently known. I do think you can even break the low and show that for certain problems it is possible to construct a polynomially-bounded algorithm that would work beneath certain N and then you can show that if N will be raised your algorithm can self-adjust itself and start to loose only certain % of instances which will be left unsolved. You can show that it can work for any finite case, the natural barrier will be easier to bypass on this ground.
Ivan, phrase it like this: “If a problem is simple to state and its solution is simple to verify, shouldn’t it naturally follow that it can be simple to solve?”
Dear Craig:
Interesting comment. I like your “If a problem has polynomial size and its solution can be verified in polynomial time, shouldn’t it naturally follow that it can be solved in polynomial time?” Indeed.
Best
Dick
I was thinking about the same thing for a long time trying to answer this question. And I think that I have one fundamental objection. I call it “asymmetrical property”. Sometimes some objects can’t show their properties because of the fundamental limitations of the systems they are defined within. Obviously, one can derive dozens of different models(=systems) which could show that property naturally, but it makes related math inconsistent for most of the time. I tried to bypass this weakness with L-Functions. They allow me to restate PvsNP in the realm of number theory and obtain a natural formulation of “Asymmetrical property”, which can be used to find better bounds. I can’t explain it all right now, but I’ll try to establish some actual lower bounds in the next half of the year in my first paper. I’m not sure that anyone will be interested at all, but I will try to post some papers for some time. I estimated that complete proof of P!=NP requires 300+ pages with 50+ or more serious theorems, which is not doable by non-mathematician like me. But when to stop? How can I realize that everything that I do is worthless and I’m simply deluded?
Magic tricks work on the basis that P != NP. Almost every magic trick has a simple stupid explanation, yet they fool people, because simple problems (how did the magician do it?) which have simple stupid solutions are not always easy to figure out. (The illusion maker Jim Steinmeyer said, “Magicians guard an empty safe.”)
Also, laymen who are fooled by magicians usually believe that the magician is using some very complicated techniques or has incredible dexterity, because intuitively they believe that P=NP, that a problem that is difficult to solve and is easy to state (how did the magician do it?) must have a complicated solution.
The answer here is simple. Mathematics wasn’t made to fool people on purpose. All of its tricks are about cleverness and clarity. Try to take a look at reversal case. FLT and others, they show that simple problems which have simple formulations can have unexpectedly large complexity
As Goedel formulated this attitude, “for clear questions posed by reason, reason can also find clear answers.”
P!=NP can also a very depressing idea. I got into mathematics, because I thought by studying mathematicians one could eventually be able to solve any problem. But P!=NP means not only will I not be able to solve any problem, but there are problems in which the solution can be almost right in front of me and I will not even see it. So I ask what is the point of studying math?
Dear Craig:
Hard problems can be depressing—I agree. But we can solve many problems, and that is exciting I would say. Th point of studying math is:
1. It is fun. 2. It is beautiful. 3. It is surprising.
I hope you enjoy it—mean math.
Best
Dick
Dick,
1. Math is fun, but so are games and sports.
2. Math is beautiful, but so is art and music.
3. Math is surprising, but so is a Hitchcock movie or a good novel.
But one thing math is that nothing else is is it is the language of nature. You cannot understand nature without understanding math. So perhaps this is the point of studying math.
If P=CH then would NC=CH or P=PSPACE be the truth? We hope truth is the latter possibility.
No comments on this? I think NC=CH is truth.
It would be really nice to know where your instinct on this would be if P=CH holds true. I think it is NC=CH.
I agree that coding the reduction would increase our confidence in the proof. However, couldn’t there also be valid non-constructive proofs if P=NP? Or reductions that are galactic even for small cases?
Of course I would imagine that the majority of proofs put forward are constructive and checkable for small problems, so your advice is a good filter.
Dear Spencer:
Yes many proofs are very constructive. The reason behind the post. But of course the proof could start with: Let us pick a huge expander graph and take the product of it with this graph 100 times and…
By thanks on the comment about it being good filter. Like that way of stating it.
Best
Dick
Supplying code with a claim, even if the program works, doesn’t mean verifying the claim is easy.
For instance, on the P vs NP wikipedia page, there is an algorithm due to Levin which solves the SUBSET-SUM problem and runs in polynomial time if and only if P=NP. Imagine if instead someone just submitted that and claimed it ran in polynomial time. How would evaluate the claim? In this case, evaluating the claim is as hard as the P vs NP problem itself.
P.Peng What you ask of is an unreasonable problem to confirm even if his algorithm has a reasonable run time. Provide him a problem where you really know variables remain linear in blowup and only remain in 100’s of non-deterministic bits (I find hard to find such cryptographic examples with what is known in the usual world of research and so you have to cook him an example and do a ZKP and that is likely the only way)?
P.Peng What you ask of is an unreasonable problem to confirm even if his algorithm has a reasonable run time. Provide him a problem where you really know variables remain linear in blowup and only remain in 100’s of non-deterministic bits (I find hard to find such cryptographic examples with what is known in the usual world of research and so you have to cook him an example and do a ZKP and that is likely the only way)?
Dear L:
Not sure get your comment. I am not saying that the claimer must supply a fast run time. I am saying that coding it and even working on trivial examples would be powerful. The examples can be tiny. Thus my thesis is this:
A mistaken claim about a reduction from SAT to say solving LP’s is wrong because it just does not work. Even for tiny examples.
This is based on seeing many claimed proofs. It is not a theorem, of course.
Best
Dick
I thought the goal is to convince the verifier of the prover’s sanity not convincing the prover of his insanity.
I thought the goal is to convince the verifier of the prover’s sanity not convincing the prover of his own insanity.
Any solution of P vs NP problem will never be published in peer-reviewed journals
or somehow officially accepted. So it’s better to be focused on other
problems.
Is the goal of computer science research getting a paper published in a peer-reviewed journal or is it to understand computer science?
Dear L:
I like the direct question. Usually the latter, insight; but the publishing pressure is strong on many.
Best
Dick
A follow up question: Nowadays, people judge scientists by how many papers and books they write – in general, the more papers and books the scientist writes, the more knowledgeable the scientist.
But shouldn’t it be the opposite? The more papers and books the scientist reads, the more knowledgeable the scientist?
And which is greater?
1) The total number of science books and papers written.
or
2) The total number of times people besides the authors have read science books or papers.
Now the preprint
https://www.preprints.org/manuscript/201908.0037/v1
has the GitHub Repository link.
Rephrasing Descartes:
I prove, therefore I code!!!
I proved, I coded and later, what else?
Dear vegafrank:
Great to have coded. Did you run the code on examples?
Best
Dick
Dear Professor,
I created some unit test in the project with examples. Besides, I programmed the assertion of the instances, so every time a reduction ia done, the assertions are validated. Unfortunately, my reduction requires a certificate: see more in my previous comments, the paper and the GitHub project, so you would understand the idea of my assumption and why I think it could help to solve P vs NP.
Best,
Frank
Three journals have rejected my paper in less than two days without peer-reviewing it at all and the three ones gave similar responses, something such as: “We’re unable to consider your submission. We are sorry…”
Nobody has not answered my two challenged comments of finding a flaw in the proof here.
I think something smells fishy, isn’t it?
Vegafrank, from one P vs. NP enthusiast to another, you are playing a game with different rules than you think they are. It took me a long time to figure out the rules of the game.
First of all, this P vs NP problem is a unique problem. If you want to convince people that they are equal, you will fail, because they are not equal. But if you want to convince people that they are not equal, you will also most likely fail because it is human psychology to not want to admit defeat, that there are easy to state problems that are difficult to solve, even if they have easy to verify solutions. My experience is that no matter what arguments one presents that P is not NP, the listener will say “maybe if you do x,y,z you will succeed and get a polynomial time algorithm”. The listener almost always thinks that he is clever enough to get around your proof by just mentioning a strategy that the proof does not mention explicitly and believing that this is enough to break the proof, even if it doesn’t break the proof.
I have not seen much difference between trying to convince an expert in computer science that P is not NP and trying to convince an angle trisector that what he is doing is impossible.
Most experts believe that P=NP in their hearts and do not want P not equal to NP to be true, so they will not take seriously any proof that they are unequal, even if they say they do.
Now you might say to yourself, “but these are not angle trisectors, these are experts.”
And I will respond, “Yes, they are experts, but they are also human beings.”
Craig, your point of view is very interesting!!! Thanks for sharing it!!!
To give an example of how difficult it is to convince experts that P is not NP, I once sent a very short paper (1 to 2 pages) to a journal with an argument that P is not NP, in which the anonymous reviewer said it was impossible that there could be such a short and simple solution to such a difficult problem.
I responded to the editor that obviously the reviewer was prejudiced that P=NP, since only someone who believes that P=NP would say that it is impossible that there could be such a short solution to a difficult problem, as such a statement is essentially logically equivalent to P=NP.
This irony was lost on the editor, as I recall, and the editor still rejected it.
It is normal that people may be suspicious of short solutions. However, this should not be taken as an argument to reject or for not considering to review. I don’t remember well, but the paper of the incompleteness theorem of Godel has few pages. This few pages changed the world for yesterday, now and so on…
I mean “fishy” in a positive way: none has found a detail in the proof which support a flaw. I submitted a new version to the preprints and I changed slightly the programming code. You could view the possible new replacements here:
https://www.preprints.org/manuscript/201908.0037
All the best,
Frank
He only claims following: ‘In this work, we show some results that might help us to solve one
of the most important open problems in computer science’. Perhaps should be peer reviewed. Would FOCS or STOC review such paper or follow the usual procedure of garbage bin? Perhaps he should cut down all the blabber on Turing, $1million etc and submit core results. People may look at it.
Dear L:
I agree on decreasing the extra comments on history and millions etc. I still would like to see the code run on examples. Lost of them.
Best
Dick
Dear Professor,
The core results are in the sections “Problems” and “Results”: they are only less than 5 pages. The result of the paper is in 4 theorems from Theorem 9 to Theorem 12. The section “Problems” covers 1 page with the definitions of all the problems of the paper. The main result is in these 4 theorems in the next remaining less than 4 pages.
It could find the unit test with the necessary examples in:
https://github.com/frankvegadelgado/VerifyReduction/tree/master/src/test/scala/frank/problems
Everybody is welcome to push new examples or fixing bugs on possible pull requests on the GitHub Project. Professor Lipton, you asked for a possible code in Python, so you would need to install Python to do that. In Scala is the same, you need to install JDK 8. In addition, in my case you need to install SBT to run the unit test (you could run the unit test with “sbt test” command). I could avoid the people to install SBT, but they might not wish to see the predefined test, but add new ones and change them.
Best,
Frank
We already know that the Theorem 9 is correct.
What about the other theorems 10, 11 and 12?
There is no proof without a prover and the checkers.
Let’s see the progress on provers and checkers
The prover:
1-He wrote a pdf proof!
2-He coded the proof!
3-He provided tiny examples for testing!
4-He convinced of a wrong claim from a possible error in the proof!
The checkers:
1-They asked for a code!
2-They asked for tiny examples!
4-They proposed the removal of extra information in the paper!
It seems that there are 4 tasks made by a single prover and 3 whole tasks made by multiple checkers.
Might this indicate that P vs NP has been solved?
Stephen Colbert will enjoy jokes.
Rephrasing Galilei,
“And yet it moves”.
My claims of a possible proof of P vs NP, in fact, move.
https://www.preprints.org/manuscript/201908.0037/v1
Now, it is simplified with less definitions and less theorems. I also updated the code in GitHub.
See more in
https://www.preprints.org/manuscript/201908.0037/v1
And
https://github.com/frankvegadelgado/VerifyReduction
Now, it is simplified with less theorems and less definitions.
https://www.preprints.org/manuscript/201908.0037/v1
Professor Lipton,
Now, the section “Results” inside of the paper has only two pages, so reading and understanding my paper it would be easier for everybody.
The proof is still in
https://www.preprints.org/manuscript/201908.0037/v1
You mentioned the removing of extra information in the paper. Now, the latex source of the paper is available inside of the GitHub project here:
https://github.com/frankvegadelgado/VerifyReduction/tree/master/doc
Therefore, any change that you may prefer or suggest can be done by a pull request into the project. You and the readers of this blog are welcomed to do it.
Thanks in advance!!!
Professor Lipton and Regan,
Now, the section “Results” inside of the paper has only two pages, so reading and understanding my paper it would be easier for everybody.
The proof is still in
https://www.preprints.org/manuscript/201908.0037/v1
You mentioned the removing of extra information in the paper. Now, the latex source of the paper is available inside of the GitHub project here:
https://github.com/frankvegadelgado/VerifyReduction/tree/master/doc
Therefore, any change that you may prefer or suggest can be done by a pull request into the project. You and the readers of this blog are welcomed to do it.
Thanks in advance!!!
Dear Professor,
Now, the section “Results” inside of the paper has only two pages, so reading and understanding my paper it would be easier for everybody.
The proof is still in
https://www.preprints.org/manuscript/201908.0037/v1
You mentioned the removing of extra information in the paper. Now, the latex source of the paper is available inside of the GitHub project here:
https://github.com/frankvegadelgado/VerifyReduction/tree/master/doc
Therefore, any change that you may prefer or suggest can be done by a pull request into the project. You and the readers of this blog are welcomed to do it.
Thanks in advance!!!
it’s a pretty simple/subtle error. you can’t do nondeterministic reductions. (here’s someone making the same mistake to prove that NP=co-NP: https://cs.stackexchange.com/questions/22204/why-doesnt-a-time-cutoff-convert-np-problems-into-co-np?rq=1)
props for the well-done writing tho. at least, I found it easy to follow.
Am I afraid you are confusing the terms.
I didn’t use a nondeterministic reduction.
I would explain you well @zon, so everybody could understand it. It is easy to explain. We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a Turing machine that runs in polynomial time in the length of w and c (the certificate) is
polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space
class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to
the left).
In the paper was proved that we can define a NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that it is
placed in the special tape in M that is read only and read at once.
This proof is contained into only two pages and as Professor Lipton well say the other part is only history and definitions for the introduction of the arguments. In addition, in the GitHub project is implemented the proof in the Scala language and tested with Unit Test. Since the
logarithmic space composition reduction can be done in logarithmic space, then this might be an evidence of the NP-complete L2 should be in NL and thus in P since NL is contained in P. I mean we might obtain the existence of a logarithmic space verifier M’ such that the
NP-complete problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in logarithmic space. I used the word “might” here in this blog because this would be a huge result as Professor Lipton well say and maybe this last part is not whole accurate (this conclusion is not in the paper for that reason).
That’s all!!!
Thanks in advance,
Frank
Dear Professor Lipton,
Following your advice in previous post, I offer 10 euros for any who find a flaw in my proof
(until December of 2019)
https://www.preprints.org/manuscript/201908.0037/v1
Enjoy the challenge!!!
Dear Lipton,
I updated the GitHub project simulating a logarithmic space composition. Now, the examples are more clear to understand them.
See more in
https://github.com/frankvegadelgado/VerifyReduction
Dear dick,
Now, I closed the offer of 10 euros (nobody showed a flaw). In addition, I added more content to the proof and now we can say the proof claims that P = NP. The whole argument is easy to explain. We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a deterministic Turing machine that runs in polynomial time in the length of w and c (the certificate) is polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to the left).
In the paper was proved that we can define a NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a deterministic Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that c is placed in the special tape in M that is read only and read at once.
Since the logarithmic space composition reduction can be done in logarithmic space, then this might be an evidence of the NP-complete L2 is in NL and thus in P since NL is contained in P. We can obtain the existence of a logarithmic space verifier M’ such that the NP-complete problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in logarithmic space. The existence of N is possible because N could be a deterministic one-way logarithmic space Turing machine.
Certainly, the languages accepted by a deterministic one-way logarithmic space Turing machine coincide with the class L. A deterministic one-way logarithmic space Turing machine is not allowed to move the input head to the left. We already know every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. In this way, a space constructible strongly f logarithmic space-bounded is a logarithmic space computable function as well (The space constructible strongly mode means that the space is bounded by the condition that, given a function f, the Turing machine uses at most f(i) cells of the work tapes in any configuration with input head at position i, occurring in any accepting computation).
Since N is a deterministic one-way logarithmic space Turing machine, we do not have to reset the computation of M(w, c) into the whole computation of M'(w, c) = N(M(w, c)). If any single NP-complete problem can be solved in polynomial time, then P = NP. Since L_{2} is in P and L_{2} is in NP-complete, then we obtain the complexity class P is equal to NP.
See more about the proof in
https://www.preprints.org/manuscript/201908.0037
In the following GitHub project is implemented the proof in the Scala language and tested with Unit Test.
https://github.com/frankvegadelgado/VerifyReduction
That’s all!!!
Thanks in advance,
Frank
https://github.com/frankvegadelgado/VerifyReduction/blob/master/README.md
Dear dick,
I have fixed the result since the statement “Certainly, the languages accepted by a deterministic one-way logarithmic space Turing machine coincide with the class L.” could be false. Here is the new proof with the fixed arguments:
We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a deterministic Turing machine that runs in polynomial time in the length of w and c (the certificate) is polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to the left).
In this project was proved that we can define a NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a deterministic Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that c is placed in the special tape in M that is read only and read at once.
We can simulate the computation M(w, u) = y by a nondeterministic logarithmic space Turing machine N, such that N(w) = y since we can read the certificate string u within the read-once tape by a work tape in a nondeterministic logarithmic space generation of symbols contained in u. Certainly, we can simulate the reading of one symbol from the string u into the read-once tape just nondeterministically generating the same symbol in the work tapes using a logarithmic space.
Hartmanis and Mahaney have investigated the classes 1L and 1NL of languages recognizable by deterministic one-way logarithmic space Turing machine and nondeterministic one-way logarithmic space Turing machine, respectively. If we suppose that L is a proper subset of 1NL, then we can accept the elements of the language L1 in L by a nondeterministic one-way logarithmic space Turing machine M’. In this way, there is a nondeterministic logarithmic space Turing machine M”(w) = M'(N(w)) which will output 1 when w is in L2. Consequently, M” is a nondeterministic logarithmic space Turing machine which decides the language L2. The reason is because we can simulate the output string of N(w) within a read-once tape and thus, we can compute in a nondeterministic logarithmic space the logarithmic space composition using the same techniques of the logarithmic space composition reduction, but without any reset of the computation. Certainly, we do not need to reset the computation of N(w) for the reading at once of a symbol in the output string of N(w) by the nondeterministic one-way logarithmic space Turing machine M’. Therefore, L2 is in NL and thus, L2 is in P due to NL is a subset of P. If any single NP-complete problem can be solved in polynomial time, then P = NP. Since L2 is in P and L2 is in NP-complete, then we obtain the complexity class P is equal to NP under the assumption of L is a proper subset of 1NL.
Hartmanis and Mahaney have also shown with their result that if 1NL is a subset of L, then L=NL, because they proved there is a complete problem for both 1NL and NL at the same time. If this way, if L is not equal to NL, then L is a proper subset of 1NL by contraposition. Since we already obtained that P = NP under the assumption of L is a proper subset of 1NL, therefore if L is not equal to NL, then P = NP. Hence, if P is not equal to NP, then L = NL by contraposition. Consequently, L = NL and P = NP cannot be both true or false at the same time and thus, L is not equal to NP.
I have updated instantly in:
https://www.academia.edu/39973754/Logarithmic_Space_Verifiers_on_NP-complete
There will be later updates in:
https://www.preprints.org/manuscript/201908.0037
https://hal.archives-ouvertes.fr/hal-02199310
That’s all!!!
Thanks in advance,
Frank
Sorry the real result is:
L = NL and P = NP cannot be both false at the same time.
See more in:
https://www.academia.edu/39973754/Logarithmic_Space_Verifiers_on_NP-complete
Dear dick,
I have proved that if L is not equal to NL, then P = NP..
In addition, I have demonstrated that L is not equal to NL.
Hence, we obtain that P = NP.
See more in
https://www.preprints.org/manuscript/201908.0037
Dear dick,
This is our Proof from https://www.preprints.org/manuscript/201908.0037 :
We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a deterministic Turing machine that runs in polynomial time in the length of w and c (the certificate) is polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to the left).
In this project was proved that we can define a NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a deterministic Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that c is placed in the special tape in M that is read only and read at once.
We can simulate the computation M(w, u) = y by a nondeterministic logarithmic space Turing machine N, such that N(w) = y since we can read the certificate string u within the read-once tape by a work tape in a nondeterministic logarithmic space generation of symbols contained in u. Certainly, we can simulate the reading of one symbol from the string u into the read-once tape just nondeterministically generating the same symbol in the work tapes using a logarithmic space.
Hartmanis and Mahaney have investigated the classes 1L and 1NL of languages recognizable by deterministic one-way logarithmic space Turing machine and nondeterministic one-way logarithmic space Turing machine, respectively. If we suppose that L is a proper subset of 1NL, then we can accept the elements of the language L1 in L by a nondeterministic one-way logarithmic space Turing machine M’. In this way, there is a nondeterministic logarithmic space Turing machine M”(w) = M'(N(w)) which will output 1 when w is in L2. Consequently, M” is a nondeterministic logarithmic space Turing machine which decides the language L2. The reason is because we can simulate the output string of N(w) within a read-once tape and thus, we can compute in a nondeterministic logarithmic space the logarithmic space composition using the same techniques of the logarithmic space composition reduction, but without any reset of the computation. Certainly, we do not need to reset the computation of N(w) for the reading at once of a symbol in the output string of N(w) by the nondeterministic one-way logarithmic space Turing machine M’. Therefore, L2 is in NL and thus, L2 is in P due to NL is a subset of P. If any single NP-complete problem can be solved in polynomial time, then P = NP. Since L2 is in P and L2 is in NP-complete, then we obtain the complexity class P is equal to NP under the assumption of L is a proper subset of 1NL.
Hartmanis and Mahaney have also shown with their result that if 1NL is a subset of L, then L=NL, because they proved there is a complete problem for both 1NL and NL at the same time. If this way, if L is not equal to NL, then L is a proper subset of 1NL by contraposition. Since we already obtained that P = NP under the assumption of L is a proper subset of 1NL, therefore if L is not equal to NL, then P = NP.
The class 2L contains those languages that are deterministic logarithmic space reduced to a language in 1L. The class 2NL consists in those languages that are nondeterministic logarithmic space reduced to a language in 1NL. We obtain that 2L is a subset of L and 2NL is a subset of NL by the definition of L and NL under the L-reduction and NL-reduction, respectively. Certainly, since the output string will be in 1L or 1NL, then we do not need to reset the computation of the L-reduction or NL-reduction in order to be decided by a deterministic or nondeterministic logarithmic space Turing machine under logarithmic space composition, respectively.
On the one hand, every language in L’ in L which is decided by a deterministic logarithmic space Turing machine M could be L-reduced to a language in 1L. The reason is simple, because the Turing machine M could output the sequence of symbols that is read continuously in the input tape during the whole computation in case of acceptance. Indeed, for every read symbol in the input tape in M, then this is written to the output tape in a sequential way. In this way, the output string could be accepted by a deterministic one-way logarithmic space Turing machine, that would be the same Turing machine M where this one will always read on the input tape from left-to-right. Certainly, when M tries to move the head of the input tape to the left into the output string, then this will move contiguously to the right. Consequently, M in case of acceptance will output the strings that consist in a language in 1L. Hence, we obtain that L is a subset of 2L. Since we already know that 2L is a subset of L, then L = 2L.
On the other hand, every language in L” in NL which is decided by a nondeterministic logarithmic space Turing machine N could be NL-reduced to a language in 1NL. The reason is simple, because the Turing machine N could output the sequence of symbols that is read continuously in the input tape during the whole computation in case of acceptance. Indeed, for every read symbol in the input tape in N, then this is written to the output tape in a sequential way. In this way, the output string could be accepted by a nondeterministic one-way logarithmic space Turing machine, that would be the same Turing machine N where this one will always read on the input tape from left-to-right. Certainly, when N tries to move the head of the input tape to the left into the output string, then this will move contiguously to the right. Consequently, N in case of acceptance will output the strings that consist in a language in 1NL. Hence, we obtain that NL is a subset of 2NL. Since we already know that 2NL is a subset of NL, then NL = 2NL.
In this way, if L = NL then 2L = 2NL. However, we know that 2L is not equal to 2NL because of 1L is not equal to 1NL since Hartmanis and Mahaney have shown that 1L is not equal to 1NL by looking at a uniform variant of the string non-equality problem from communication complexity theory. Therefore, we prove the complexity class L is not equal to NL. Since we show that L is not equal to NL, then we prove the complexity class P is equal to NP.
Best regards,
frank
https://youtu.be/7t5MST33atw
Dear dick
I have modified the proof in the following way:
We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a deterministic Turing machine that runs in polynomial time in the length of w and c (the certificate) is polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to the left).
In this project was proved that we can define an NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a deterministic Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that c is placed in the special tape in M that is read only and read at once.
We can simulate the computation M(w, c) = y by a nondeterministic logarithmic space Turing machine N, such that N(w) = y since we can read the certificate string c within the read-once tape by a work tape in a nondeterministic logarithmic space generation of symbols contained in c. Certainly, we can simulate the reading of one symbol from the string c into the read-once tape just nondeterministically generating the same symbol in the work tapes using a logarithmic space.
Hartmanis and Mahaney have investigated the classes 1L and 1NL of languages recognizable by deterministic one-way logarithmic space Turing machine and nondeterministic one-way logarithmic space Turing machine, respectively. If we suppose that L is a proper subset of 1NL, then we can accept the elements of the language L1 in L by a nondeterministic one-way logarithmic space Turing machine M’. In this way, there is a nondeterministic logarithmic space Turing machine M”(w) = M'(N(w)) which will halt in the acceptance state when w is in L2. Consequently, M” is a nondeterministic logarithmic space Turing machine which decides the language L2. The reason is because we can simulate the output string of N(w) within a read-once tape and thus, we can compute in a nondeterministic logarithmic space the logarithmic space composition using the same techniques of the logarithmic space composition reduction, but without any reset of the computation. Certainly, we do not need to reset the computation of N(w) for the reading at once of a symbol in the output string of N(w) by the nondeterministic one-way logarithmic space Turing machine M’. Therefore, L2 is in NL and thus, L2 is in P due to NL is a subset of P. If any single NP-complete problem can be solved in polynomial time, then P = NP. Since L2 is in P and L2 is in NP-complete, then we obtain the complexity class P is equal to NP under the assumption that L is a proper subset of 1NL.
Hartmanis and Mahaney have also shown with their result that if 1NL is a subset of L, then L=NL, because they proved there is a complete problem for both 1NL and NL at the same time. If this way, if L is not equal to NL, then L is a proper subset of 1NL by contraposition. Since we already obtained that P = NP under the assumption that L is a proper subset of 1NL, therefore if L is not equal to NL, then P = NP.
The class LNL contains those languages that are decided by a nondeterministic logarithmic space Turing machine N such that for every element x = yz of these languages, there are a prefix and suffix substrings y and z where N moves strictly deterministically on y and strictly nondeterministically on z when strictly deterministically means there is no a possible nondeterministic step and strictly nondeterministically means there is at least one nondeterministic step on the computation.
Sauerhoff has shown the class BNL of languages recognizable by nondeterministic logarithmic space Turing machine, that only use nondeterministic moves before reading their input (“nondeterminism at the beginning”).
We have that NL is a subset of LNL, because the prefix y of an instance x = yz could be the empty string. Certainly, all the languages in the class NL could be decided by nondeterministic logarithmic space Turing machines such that they always do a single nondeterministic step after the original acceptance state choosing nondeterministically the same acceptance state within two equals choices from the original and modified deterministic or nondeterministic logarithmic space Turing machines which decide these languages (this is assuming the prefix string y is the empty string in the elements x = yz). Moreover, we have that LNL is a subset of NL, because the languages in LNL are decided by nondeterministic logarithmic space Turing machines. Since NL is a subset of LNL and LNL is a subset of NL, then the complexity class LNL is equal to NL. However, we can state that BNL is not equal to LNL, because there is no possible way over the Definition of LNL for an element x = yz when the prefix y is the empty string in some languages in BNL, such that we could move strictly nondeterministically on y (that would be a “nondeterminism at the beginning”) and move strictly deterministically on the nonempty string z. Hence, we obtain that BNL is not equal to NL by transitivity. Nevertheless, Sauerhoff has also shown that L is a subset of BNL and BNL is a subset of NL. Consequently, we prove the complexity class L is not equal to NL. Since we show that L is not equal to NL, then we prove the complexity class P is equal to NP.
You could see the proof at:
https://www.academia.edu/39973754/Logarithmic_Space_Verifiers_on_NP-complete
This will be updated soon in:
https://www.preprints.org/manuscript/201908.0037
https://hal.archives-ouvertes.fr/hal-02199310
That’s all
Thanks in advance,
frank
We can define an NP problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in P, M is a deterministic Turing machine that runs in polynomial time in the length of w and c (the certificate) is polynomially bounded by w. This is easy to prove since the polynomial time composition reduction can be done in polynomial time. Therefore, the previous definition complies with the existence of a polynomial time verifier M’ such that the NP problem L2 is defined as
L2 = {w: M'(w, c) = “yes”} (“yes” is the acceptance state)
where the computation of M'(w, c) is equal to N(M(w, c)) when N is the Turing machine which accepts L1 in polynomial time. On the other hand, the verifier for a language in NL (nondeterministic logarithmic space class) has as premise that the certificate c is placed in a special tape that is read only and read at once (that means we cannot read to the left).
In this project was proved that we can define an NP-complete problem as
L2 = {w: M(w, c) = y where y is in L1} (y is the output in the halting state)
when L1 is a language in L (deterministic logarithmic space class), M is a deterministic Turing machine that runs in logarithmic space in the length of w and c (the certificate) is polynomially bounded by w such that c is placed in the special tape in M that is read only and read at once.
We can simulate the computation M(w, c) = y by a nondeterministic logarithmic space Turing machine N, such that N(w) = y since we can read the certificate string c within the read-once tape by a work tape in a nondeterministic logarithmic space generation of symbols contained in c. Certainly, we can simulate the reading of one symbol from the string c into the read-once tape just nondeterministically generating the same symbol in the work tapes using a logarithmic space.
Hartmanis and Mahaney have investigated the classes 1L and 1NL of languages recognizable by deterministic one-way logarithmic space Turing machine and nondeterministic one-way logarithmic space Turing machine, respectively. If we suppose that L is a proper subset of 1NL, then we can accept the elements of the language L1 in L by a nondeterministic one-way logarithmic space Turing machine M’. In this way, there is a nondeterministic logarithmic space Turing machine M”(w) = M'(N(w)) which will halt in the acceptance state when w is in L2. Consequently, M” is a nondeterministic logarithmic space Turing machine which decides the language L2. The reason is because we can simulate the output string of N(w) within a read-once tape and thus, we can compute in a nondeterministic logarithmic space the logarithmic space composition using the same techniques of the logarithmic space composition reduction, but without any reset of the computation. Certainly, we do not need to reset the computation of N(w) for the reading at once of a symbol in the output string of N(w) by the nondeterministic one-way logarithmic space Turing machine M’. Therefore, L2 is in NL and thus, L2 is in P due to NL is a subset of P. If any single NP-complete problem can be solved in polynomial time, then P = NP. Since L2 is in P and L2 is in NP-complete, then we obtain the complexity class P is equal to NP under the assumption that L is a proper subset of 1NL.
Hartmanis and Mahaney have also shown with their result that if 1NL is a subset of L, then L=NL, because they proved there is a complete problem for both 1NL and NL at the same time. If this way, if L is not equal to NL, then L is a proper subset of 1NL by contraposition. Since we already obtained that P = NP under the assumption that L is a proper subset of 1NL, therefore if L is not equal to NL, then P = NP.
The class LNL contains those languages that are decided by a nondeterministic logarithmic space Turing machine N such that for every element x = yz of these languages, there are a prefix and suffix substrings y and z where N moves strictly deterministically on y and strictly nondeterministically on z when strictly deterministically means there is no a possible nondeterministic step and strictly nondeterministically means there is at least one nondeterministic step on the computation.
Sauerhoff has shown the class BNL of languages recognizable by nondeterministic logarithmic space Turing machine, that only use nondeterministic moves before reading their input (“nondeterminism at the beginning”).
We have that NL is a subset of LNL, because the prefix y of an instance x = yz could be the empty string. Certainly, all the languages in the class NL could be decided by nondeterministic logarithmic space Turing machines such that they always do a single nondeterministic step after the original acceptance state choosing nondeterministically the same acceptance state within two equals choices from the original and modified deterministic or nondeterministic logarithmic space Turing machines which decide these languages (this is assuming the prefix string y is the empty string in the elements x = yz). Moreover, we have that LNL is a subset of NL, because the languages in LNL are decided by nondeterministic logarithmic space Turing machines. Since NL is a subset of LNL and LNL is a subset of NL, then the complexity class LNL is equal to NL. However, we can state that BNL is not equal to LNL, because there is no possible way over the Definition of LNL for an element x = yz when the prefix y is the empty string in some languages in BNL, such that we could move strictly nondeterministically on y (that would be a “nondeterminism at the beginning”) and move strictly deterministically on the nonempty string z. Hence, we obtain that BNL is not equal to NL by transitivity. Nevertheless, Sauerhoff has also shown that L is a subset of BNL and BNL is a subset of NL. Consequently, we prove the complexity class L is not equal to NL. Since we show that L is not equal to NL, then we prove the complexity class P is equal to NP.
You could see more in:
https://www.academia.edu/39973754/Logarithmic_Space_Verifiers_on_NP-complete
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? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity classes are L and NL. We demonstrate if L is not equal to NL, then P = NP. In addition, we show if L is equal to NL, then P = NP. In this way, we prove the complexity class P is equal to NP.
See more in
https://www.preprints.org/manuscript/201908.0037
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? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Another major complexity classes are L and NL. We demonstrate if L is not equal to NL, then P = NP. In addition, we show if L is equal to NL, then P = NP. In this way, we prove the complexity class P is equal to NP.
See more in
https://www.preprints.org/manuscript/201908.0037
https://zenodo.org/record/3576209
https://www.academia.edu/39973754/P_versus_NP
https://hal.archives-ouvertes.fr/hal-02199310