I first saw this paper yesterday when it was posted on HN but didn't make it to the front page and I'm uncertain about how much energy to put into it (unfortunately my health gives me very little to spare). So far I've only read the introduction and it doesn't obviously involve any advanced mathematics that I'm unfamiliar with so I could perhaps attempt an implementation.
In addition to what I said above another factor arguing against investing much time in this is the fact that this was first published last year and nothing seems to have come of it in that time. Moreover it appears that the current paper is a revision from the one that was published last year. Does anyone know what the history of this was ? Were bugs found in the first version ?
This is a bad sign for the paper. The prior cases of solving big foundational problems I'm aware of all introduce substantial new math. So much so that the actual problem is something of an afterthought. Wiles's proof of Fermat's last theorem is substantial.
It's not impossible that this is legitimate, but... it seems unlikely that P=NP has evaded proof for so long if the solution were straightforward. There are also a LOT of plausible-but-flawed proofs -- it's not unsolved for a lack of trying.
I still think it's possible that there could be a relatively simple solution that has so far eluded humans. They are burdened by many individual, institutional and societal biases and I think they are far less intelligent than they generally believe.
The final complexity discussion uses the graph size constraint gained by the "improvement" but doesn't consider how to handle the extra labeling meaningfully. Basically, the pre- and post-improvement algorithms put the exponential work in different spots, and the sloppiness of the algorithm description (I mean, really, why tell us you're using a stack for BFS and then have "determine the subset of satisfied constraints" as a step) makes it easy to ignore.
I'm also being a little generous with the algorithm itself. As described, some of the trie optimizations seem to make certain combinations of satisfied expressions impossible to notice, but I think it's not a big deal to make this part work. The properties of the trie structure (and of sorting the variables by occurrence, for that matter) don't seem to be used.
The proofs and even explanations in this paper aren't very clear to me...
> Doing this enables us to represent each Di as a variable sequence, but with all the negative literals being removed. See Table I for illustration.
What justification does he have for throwing out negated variables ? If you do that the problem likely becomes trivial, but has nothing to do with the original problem.
It does create issues with determining which expressions are satisfied, since two different paths can meet at a merged trie vertex higher up, which requires the extra bookkeeping that kills it.
Remember the "faster than light neutrinos" thing? They published their stuff basically saying "Okay, we're really uncomfortable with this result so can someone explain what we've missed here?".
Papers like this always feel like the author is surprised anyone is even doubting them. "What, it's just the hardest problem in your field, worthy of a Millennium prize, and I'm publishing it in some lesser-known journals with little peer review. What of it?"
Come on. Have some modesty. Have some self-doubt! Reach out to Terry Tao and you know he'll happily explain your mistake and then help you write a better paper.
> Here, we notice that if we had one more span, <v3 , v4 , v5 >, for example, it would be connected to <v1 , v2 , v3 >, but not overlapped with <v1 , v2 , v3 >. Being aware of this difference is important since the overlapped spans imply the consecutive ‘’s, just like <v1, v1, v2> and <v1, v2, v3>, which correspond to two consecutive ‘’s: (c2 , ) and (c3 , ). Therefore, the overlapped spans exhibit some kind of transitivity. That is, if s1 and s2 are two overlapped spans, the s1 ∪ s2 must be a new, but bigger span. Applying this operation to all the spans over a p-path, we will get a ’transitive closure’ of overlapped spans.
It's a pitty they don't release any source code that we can unit-test against problems with known solutions (while also profiling run-time to stay within polynomial bounds) :)
edit: what am I missing, their reduction to a DNF seems unsuitable to me?
I read proposition 1 [1] to mean: they find an optimal solution for the DNF V∪X, then expect the corresponding CNF C to have at least as many satisfied clauses. However isn't that insufficient? I mean there could be an even better solution with more satisfied clauses in C, that are totally missing when only looking for solutions for V∪X. But maybe I'm just misunderstanding something.
It looks like the paper was previously published in a relatively low impact AI conference last year. It seems like it should be in FOCS, STOC, or a prestigious math journal to have significant credibility.
(To the ones who did not waste their best years doing theoretical computer science, this was in jest - the paper most definitely contains mistakes)
I am also an amateur working on P=NP. Last week, I think I also proved that P=NP, but with a different method, and was about to seek publication.
My result seems very similar to his, yet very different. I can prove that class of SAT which is intersection of 2SAT and XORSAT is NP-complete by reduction to 3-SAT. Then I follow the approach in Melville's Krom 1967 paper on 2-SAT, and prove that certain polynomial-sized logic (that corresponds to the intersection) is refutable complete. So you can essentially generate all formulas in that logic and if you don't find contradiction, the instance is satisfiable.
I have also did some preliminary testing of my method, and was able to factor small integers with it. However, there was a bug.
So, to sum up, I am not surprised that P=NP with a constructive and efficient algorithm. Take it for what you want. The future is gonna be interesting (crypto DOOMSDAY).
The reality is yes it's an arxiv paper and I'm not a computational complexity expert so I cannot gauge it for myself.
Talk about burying the lede.
If you get a password in polynomial time you are golden.
In any case, that someone says they proved P=NP is not such a big red flag as people seem to think.
Still, there's almost certainly a mistake in this paper.
Now map a big, critical and difficult problem to the 2-Maxsat problem, solve it in polynomial time, get rich and come back to argue if it is really a proof of P = NP.
Is this serious?
(I'm leaving aside the fact that cryptocurrency theft is a crime that most people would be disinclined to commit, as well as the extraordinarily high likelihood that this proof is incorrect.)
You can target anyone's wallet in O(1) time, no proofs needed :^)
https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...
For some problems, you can pick easy instances (even if large), or there can be ways to go backwards and generate an instance you know the answer to (prime factorization comes to mind).
I believe that there's problems where it's difficult to even find a hard instance, it's just also difficult to prove that no difficult instances exist either. SAT might be one if I remember correctly, solvers actually do really well.
How does this help to support your belief that P=NP has been solved by someone else? Surely it wouldn't surprise you if it turns out they were as wrong as you were before?
PS: Also, reducing 2SAT to 3SAT doesn't help proving that P=NP. The opposite reduction would, if you were able to do the reduction in polynomial time. But maybe I misunderstood something about what you attempted.
So, I have some evidence, both experimental and theoretical, there is an efficient polynomial algorithm out there (and possibly many different methods).
Unfortunately, not 100% verified because despite what many smartypants are saying here, it's incredibly difficult to even have a conversation about a possibility of a relatively uncomplicated proof that P=NP. (I think Millenium prize is part of the problem, but that's another discussion).
And to clarify, I am reducing 3-SAT to 2XSAT, not 2-SAT. 2XSAT generalizes 2-SAT to arbitrary linear equations rather than literals (we can think of a literal as a linear equation on 1 variable).
I will happily send you (or anybody) the draft I have, so that you can critique it.
I played with propagation a lot in the past, but I don't think local propagation (that resolves conditions of a bounded number of variables at a time, until everything stabilizes) can ever work, because it would contradict Razborov result on monotone circuits. I don't remember the exact argument, but I think it would imply a polynomial monotone circuit capable of resolving the instance. Also, XORSAT is not really amenable to this either, to solve arbitrary XORSAT instance you have to add together arbitrary number of linear equations, so the number of variables per equation can balloon up.
That's why more recently I focused on understanding what exactly is the role of XORSAT, and by serendipity, I stumbled upon the above-mentioned reduction (which I think is a really exciting result). XORSAT is great for testing different algorithms, because despite the fact we have a nice polynomial algorithm (Gaussian elimination), one can easily create arbitrary (and loopy) instances where propagation is difficult.
The way I see it, to avoid the problems with the bound, you need to preprocess the linear equations "inherent" in the instance by adding extra variables. The exact way to add variables depends on the instance, but it can be done by solving the linear equations. Propagation algorithms that go into the process blindly, without understanding the underlying linear structure, will mysteriously fail.
However, my current approach through logic, basically building up theorems about the instance, until it is decided, can be considered a generalization of the propagation approaches. The messages are true statements about variables, which are propagated by deduction rules of the logic. But this is done only after we have discerned the linear structure in the problem, which is addressed globally, as described above.
The language conveniently helps us make incredibly complicated statements by using specialized terms. Simple solution are rarely that simple, once we eschew the jargon of the field.
We stand on the shoulders of giants, and all that.
If you know the private key, then you own the coins.
At least that's the whole basis that crypto currency is founded on...
How do you prevent an exponential increase in linear terms though?
Good luck!
To prevent exponential increase in linear terms, I work within a sort of limited logic that only allows formulas that are ORs of (implications between) two linear equations of up to 2 variables. This logic accommodates both 2-SAT clauses and linear clauses of 3 variables, and seems to be able to emulate Gaussian elimination to some extent, but I am not yet completely sure how. Last week, I think I was able to generalize Krom's proof of refutable-completeness for 2-SAT logic (that has linear equations on 1 variable) to this logic, but I am in the process of double checking my result for gotchas like this.
There are other ideas how to control the linear terms, once you have the linear equations solved, it's easy to verify whether some variables are linearly dependent, because you have the basis, and modify the ordinary 2-SAT algorithm accordingly (2-SAT works by propagation via transitive dependency of literals, but if the 3 variables involved are linearly dependent, then you can derive lot more). These are mainly ideas how to make the polynomial algorithm even more efficient.
And thanks for encouragement!
NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete.
Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution.
NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.
{ (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve }
Also, this algorithm is not easily parallelizable, so even O(n^5) can be an issue for n > 1000.
Also note that in this particular problem, n is a count of bits and logical ORs of pairs of bits, so getting to n > 1000 is a lot easier than you may think.
Also, I assume most people would not go through 3SAT to MAX2SAT, they would just reduce directly there.
Many NP-hard problems tend not to be NP-hard on "average"; that is, reasonable heuristics can usually find you the correct answer. But there are certain structures that are (seemingly) difficult to solve. If you can exclude these structures by construction, the problem is in P; otherwise it's NP-hard. Boolean satisfiability is a good example here.
It also turns out from combinatorics that you can sometimes force necessary order on a structure by embedding it in larger space--sheer size imposes a structure of its own. Probably the most well-known example of this is the L=SL proof (admittedly, not generally well-known), where you can guarantee a walk that will visit all connected nodes of a graph without saving any history of nodes you've visited. Just replace every node with a new graph that is of size at least (IIRC) 3^65536. It's a constant factor, even if the constant is larger than the volume of the universe measured in Planck lengths.
Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter. It follows that it isn't any more difficult to construct a hard instance of any NP-hard problem than it is to encode a more easily constructible problem into the same.
As for verifying the solution, that would be different, since it is not necessarily easy to verify the solution to a problem in OptP. I had not considered that part. But you probably don't have to go as far as importing integer factorization.
That should work if you pick something like one of the unsolved RSA challenges or something.
With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.
No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.
> With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P.
It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.
If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.
So I cannot publish that (I am well aware of the unfortunate situation that only a practical implementation will now convince people that P=NP).
Add to it, why should I? What if it's not that far from a full solution, and somebody else will get the prize?
I came to understand why Perelman refused the prize. Mathematics should be about collaborative understanding of the universe, not about people working in isolation until they have fully working superoprimized implementation that can crack Bitcoins.
NP is generally thought to be harder than factoring, so I'm not sure that your reduction is a "reduction" in the sense that you've restated factoring in a (potentially-)harder-than-native problem space. Proving that factoring is polynomial would be a huge result indeed, but if your strategy requires you to prove P=NP along the way, you're focused on the wrong problem and I wouldn't expect you to get much traction.
> Mathematics should be about collaborative understanding of the universe
If you really think mathematics should be about collaboration and not competition, why do you worry about who gets the prize?
You should pick what's more important to you - if it's collaboration, why not publish the steps you've accomplished? If someone else uses it to achieve a full solution, you'll still have a claim to part of the credit towards the solution.
1- it's easy to generate RSA-like challenges for factoring, a product of two large primes.
2- it's easy to turn these RSA-like challenges into instances of the SAT problem (the canonical NP-complete problem).
3- SAT problems can be reduced to any NP-complete problem.
4- these reductions are known, because the typical proof of NP-completeness is to provide a reduction from another NP-complete problem, which will ultimately end up with SAT if you follow the chain for long enough.
... it follows that it's not too hard to generate hard instances of any NP-complete problem, assuming that factoring itself is a hard problem.
Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.
I am reducing to 2XSAT, which is a name for instances that are intersections of 2-SAT and XORSAT instances.
Both 2-SAT and XORSAT have polynomial algorithms, why is it hard to believe that their intersection has one too?
There are other ways to improve the method, which (if indeed P=NP) are incredibly interesting - you can directly compose presolved general instances and specialize on them. Kinda like if you need to compute many solutions to linear equations, you only need to factor the matrix once.
I think testing O(n^8) algorithm is pointless, so it needs more polishing (naive algorithm for 2-SAT (that follows from Krom) is O(n^3) or so, but the best methods are linear; so I feel there is a lot of room for improvement, but obviously my method is a little bit more complicated than 2-SAT, which it generalizes).
> I am reducing to 2XSAT, which is a name for instances that are intersections of 2-SAT and XORSAT instances.
It seems to me that 2-SAT and XORSAT are distinct problems. I mean there is no problem instance that is simultaneously a 2-SAT problem and an XORSAT problem instance. So how can there be instances that are intersections of both ?
Yes, 2XSAT is the name I gave it, and I couldn't find it anywhere. The reduction is surprisingly simple, yet nobody mentions it. That's why I am warning people here - just based on this alone, I 80% believe that P=NP with a practical algorithm (which either way involves solving linear equations). And I wouldn't be surprised somebody coming up with the algorithm.
The reason why I say it's an intersection is because that's how the set of solutions of an instance looks like. That's what we need to figure out - how to characterize the sets of solutions described by SAT instance (i.e. sets of assignments to boolean variables that satisfy the instance).
However, it's not that easy, even if you characterize them as interesections of 2-SAT and XORSAT instances, set of solutions to 2-SAT is notoriously hard to characterize too, for example, #2SAT is not known. And polynomial algorithms for 2-SAT and XORSAT are doing very different things, and it's not at all obvious how to generalize them into a common algorithm that can do both.
As a grad student, I got perhaps hundreds of "dear professor" emails claiming proof of everything from squaring the circle to the BSD conjecture. Reflexively running from anybody making such claims is a necessary survival skill. Math is a field where the bullshit asymmetry principle[1] is particularly stark. Finding a flaw in a proof can take vastly more effort than is spent concocting it.
There are in fact problems that are both 2-SAT and XORSAT, but they seem to be rather trivial - those are linear equations that have up to 2 variables per equation. But that's not what I am talking about.
I understand why people are confused with my off-hand comments, but I didn't plan to explain my approach here in detail, and I typed the first couple of comments when I was at work on my phone, where being precise is tedious.
I think professionals of every field have to deal with passionate amateurs of all levels. I understand why many people don't want to do it, but IMHO overemphasis on professionalism (culturally coming from enormous peer pressures) is hurting any field. The superprizes make it even worse.
> Just don't act confident that you've cracked a keystone problem in the field.
I am not acting like that, but I also have to be honest that my goal is specific - to understand why we can or can't have a polynomial algorithm. I.e. I have a strategy already, what I need is a 2nd opinion about some specifics of it.
This is the entire question of P vs NP. I'd love to point you to a reference, but the question remains unresolved. Good hunting.