I've spent a great deal of time over the last decade+ trying to find an efficient algorithm for NP hard problems and one thing I've learned is that this field is a graveyard for seemingly good ideas. Therefore I tend to be very skeptical of any paper that claims to solve such a problem but doesn't provide any empirical evidence that their solution works. I mean I've had hundreds of ideas and very few of them have survived without counterexamples appearing even for very small instance sizes.
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 ?
> 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.
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.
That's the kind of argument I've never put much credence in, otherwise I never would have even attempted to solve the problem.
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.
Simple proofs are often only possible, because the language of mathematics become increasingly descriptive over time.
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.
Unsurprisingly, there's nothing here. Most of the paper describes a brute force search across all possible variable assignments in the form of a graph (with some pointless polynomial improvements like making it a trie), where you build a path of vertices representing each set of truth values that satisfies a given expression. This clearly has exponential size, which the author alludes to in the "improvements" section by noting it does "redundant work". This is addressed by collapsing the exponential graph down to have only one vertex for each variable*expression pair (if you ignore the trie) and adding exponentially many labels for the different paths to reach a given vertex. (incidentally, to the extent that it's described clearly, it seems like the improved layered graph would basically be the same as the original non-layered graph)
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.
I haven't really understood how the proposed simplification should work... It's clearly exponential without it, but I am not sure about the supposed added labels. What should those be, conjunction and group subsets? Does that make them exponential?
The proofs and even explanations in this paper aren't very clear to me...
I'm stuck in the III.A "Main Idea" section where he says:
> 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.
I had trouble with that too initially. I think that's actually fine: the representation the paper wants to use is that the variables in a path are the ones set to true, so omitting one means that variable must be false to satisfy the expression.
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.
I have a hard time taking seriously anyone who publishes a paper like this truly believing they've solved P=NP.
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.
For me, the following is a bit that seems particularly prone to be invalidated, even more so considering that the author doesn't present any proof of it:
> 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.
I already have problems following Proposition 1 where they introduce a different DNF with twice the clauses of the original CNF than claim that maximizing the satisfied clauses in the DNF would also yield a maximum satisfied solution for the CNF.
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.
The conversion to DNF is fine. The original clauses map directly to pairs of new clauses, so fixing an assignment to the original variables V you can always satisfy the same number of the DNF clauses. You can do worse by choosing the wrong values for X, sure, but there's always a straightforward correspondence.
Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it's a constructive proof, not just an existence proof, then presumably the author should be able to reduce some other problems to this one (2-Maxsat) and solve them as a demonstration.
I'd be more inclined to believe their P=NP claim if they used it to grab all of Satoshi's bitcoins. That should be the first order of business for anyone finding an efficient algorithm for the ECDLP (Elliptic Curve Discrete Log Problem), as implied by their constructive proof.
A proof that P=NP doesn't necessarily mean that NP-hard problems are solvable in any practical sense. The time complexity claimed by the paper, O(n^2 * m^3), grows quickly, and the constant factors may be high. In fact, I'd go so far as to say it's very unlikely that a P=NP proof would make any difference in practice, since SAT solvers are so good for real-world problems.
(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.)
Except most legal systems don’t see it that way. When you say this, they hear “if you have a copy of the key to a house/car/etc, then you also own it”. Cryptocurrency theft is a crime by the basic definitions of the legal system.
The problem of "find a series of bytes that is a valid transaction sending these bitcoins to me" is an NP problem. When you can solve arbitrary "find satisfying input" problems, details like "the public key is hashed" don't matter. It's adjusting what it means to be valid, not changing the nature of the problem to be out of scope of "find satisfying input".
The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would not provide any insight into finding a polynomial time solution for it.
Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.
It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP.
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.
I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP.
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.
> ECDLP is assumed to be in a higher complexity class than DLP.
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.
A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.
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.
Such a reduction is known to exist, but that doesn't mean it's necessarily easy to implement. It would suffice to find some large instances of 2-maxsat and solve those.
Technically (and depending on the problem, practically), giving large instances isn't a good test.
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.
>I believe that there's problems where it's difficult to even find a hard instance
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.
The RSA challenges are very easy to generate - just generate large random numbers, check if they pass a primality test like Miller-Rabin (this doesn't take long even with a naive implementation). Then multiply two of those that do pass the test (distinct ones!), and you're done.
Sure, but presumably they're difficult to solve. I'm saying that if they can _solve_ an unsolved one using this algorithm, that would certainly be compelling.
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.
Only if they're (i) conjectured hard instances (ii) for which we can verify that a given solution is indeed optimal. Which in many cases is itself is a Gödel prize worthy task.
Usually when I see these things, I check if the author seems to have the right background. Yangjun Chen is a full professor at the University of Manitoba, but he doesn't seem to work in computer science theory.
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.
Many of those journals don't take P=NP proofs because they often come from quacks. Also, I wouldn't be surprised to see the start of a full proof coming from a non-theorist. Theorists have failed to make headway on P=NP for decades, so it would be reasonable to assume that some insight from a different place would be required.
Well, this is somewhat heartbreaking for me. I haven't read the paper, but the result sounds very plausible to me.
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).
I don't understand. You said that you thought you proved P=NP, but then it turned out you hadn't.
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.
I think I have a proof, it's just not yet published. Also, the original method I was attempting contained a bug, but I understand the theory better now.
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.
Nobody wants to read your draft about an algorithm that doesn't work. Your implementation is already giving you the critique that you need. If you get it to work and it's obviously polynomial time, you'll have something to talk about.
I don't think this is quite true. Most NP-hard problems are usually solvable in polynomial time, so your algorithm looking like it runs in polynomial time doesn't tell you much.
It really depends. If you have an unbounded loop that looks like it runs in polynomial time, you're in highly questionable territory. If you have a 5-deep nest of for-loops, that's what I call "obviously polynomial time" -- if such an algorithm solves every problem you throw at it, you have hope.
As <cat-over-keyboard> already mentioned, it's not always that simple. For example, my current approach (modeled after Krom, who doesn't even have a Wikipedia page - no wonder nobody reads him!) is a more systematic search for a polynomial algorithm - construct a polynomial sized-logic in which theories have models that are satisfying instances of SAT, and prove its refutable-completeness. This proves existence of a polynomial algorithm, because you can generate all formulas of theory (coming from SAT instance) in said logic, and if you don't find a contradiction, the instance is satisfiable. The algorithm is kinda implicit, non-deterministic, if you will (because you can generate all the formulas in any order or even generate just a subset).
Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.
Sure, but most complicated polynomial time algorithms don't work like this. You either have cases like AKS which are obviously polynomial but not obviously correct, or cases that are obviously correct but not obviously polynomial.
Algorithms which are obviously polynomial, and non-obviously correct are the only ones I'd entertain from a novice. It's not hard to mine for counterexamples, as long as the code runs.
I think this is exactly the unhelpful tactics that have prevented people figuring out the problem. I have both theoretically and practically verified the 2XSAT reduction, and I believe it's a step towards P=NP. But, it's being dismissed out of hand because I don't have a practical, fully polynomial, algorithm.
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.
> I have both theoretically and practically verified the 2XSAT reduction, and I believe it's a step towards P=NP.
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.
If your reduction can solve factoring, what are the factors of 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199?
I already said, I don't have an efficient algorithm. Once I will have, in my estimation, at best, it will be O(n^3) (n is number of variables), which still means a lot - to factor 16-bit integer, my (linear) 2XSAT reduction requires about 4000 variables, so the number of variables for a cryptographically-strong problem will be in millions. You need to have a very efficient parallel algorithm to deal with that, and that's very low on the list of priorities - first I need to understand how to actually make the algorithm efficient (so far I think I proved there is a polynomial bound - around O(n^8) or so, but I know for sure it's very inefficient, because I am doing it very naively).
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.
Why don't you try testing your algorithm on some 1000 variable or so SAT instances ? There are thousands of such problems that have been created for the SAT competitions. If your code can solve all of them and is really P-time then I think there are many people who would be interested in looking at your algorithm, myself included.
That's what I am generally doing and planning to do, however right now, the theory had priority (there is still couple weak spots in my proof which I need to patch up). But I will return to testing once I will have a better idea what I want the algorithm to do (as I mentioned, a more naive version of the method that combined solving 2-SAT and XORSAT failed with a bug, which I think I now understand).
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).
There's one thing I'd like to get some clarification on. You said in an earlier comment:
> 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 ?
The 2XSAT has clauses that are from 2-SAT or XORSAT. So it's a generalization of both. The solutions (boolean variable assignments) must satisfy both 2-SAT and XORSAT part of the problem, hence the solutions of the 2XSAT instance is their intersection.
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.
No, you misunderstand, the intersection is in the solution to the instance. The 2XSAT are problems that can contain both 2-SAT clauses (two literals per OR clause) and XORSAT clauses (linear equations). 2-SAT (as well as XORSAT) are just special cases of that. You can also think of it as 2-SAT, but confined into a linear subspace of Z_2^n.
That isn't the intersection of 2SAT and XORSAT, it's the union. Problems in the intersection would be solvable by either type of solver. I don't think it's "obvious" that your problem class should be polynomial; 2XSAT as you've described it (is it your own invention? I haven't found a reference) appears to be a strictly more powerful problem class.
It's not a union of those classes, it's a different class, and as you say, it's more powerful, because it can be projected (my reduction adds additional variables) into 3-SAT and SAT instance.
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 mathematician, my advice to you is to build up some theory around this problem class. I find it entirely plausible that you can reduce 3sat to it. I'd encourage you to look for a reduction from 2XSAT to 3sat. Find some problems that are well-expressed in the language of 2XSAT. You might find something worthy of publication. From there you'll want to shop your results around at conferences. You may drum up some interest in your work, or even a collaborator. Just don't act confident that you've cracked a keystone problem in the field. You think you're on the right path, and that's exciting, but we've all been there and we've all met dozens of novices who were utterly convinced of their incorrect solution to this problem. It's a huge red flag that you're a waste of time.
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.
The opposite reduction from 2XSAT to SAT is obvious, it's just a special case.
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.
Honestly, I don't think you have the proof.
Proving p is euqal to np will have very big consequences, not only in computer science but also in logics for example.
I think this problem is far more complex than you think and it is not going to be solved by chance by an amateur. If it's going to be solved, there will be a deep math argument.
> 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.
Because I am also a human. I think I could still use the money (if anything, very few people want to be principled idiots who refuse $1m), and if I spent several years determined to understand it, perhaps it's worth spending some more to understand it fully. As I explained, it creates an atmosphere that prevents collaboration - it's incredibly hard to find anyone to talk about the problem with. Anyway, I am writing about my approach here, and I am about to write about it more. Still, people dismiss it outright.
I haven't really studied it in detail, but my motivation is similar, I see SAT as a simplified version of the marginal problem, and I want to solve marginal problem (or at least approximate) because I am interested in representing knowledge intensionally.
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.
That jives with my intuition. I had forgotten about the connection between Gaussian elimination and xor sat. That does sound like a good direction to reason from.
How do you prevent an exponential increase in linear terms though?
I am still not sure about the exact role of Gaussian elimination. I thought that it will be somehow necessary, but it seems that if you only break linear equations to 3 variables per equation (by adding extra variables), you can get away without it. Although it certainly doesn't hurt to do it, I think for efficient algorithms, it will be required (and so the whole endeavor will be at least O(n^3)).
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.
>By the MAXSAT problem, we are given a set V of m variables and a collection C of n clauses over V. We will seek a truth assignment to maximize the number of satisfied clauses. This problem is NP-hard even for its restricted version, the 2-MAXSAT problem by which every clause contains at most 2 literals. In this paper, we discuss a polynomial time algorithm to solve this problem. Its time complexity is bounded by O(n2m3). Hence, we provide a proof of P = NP.
The first step is to encode some decent password cracking challenge into an NP complete problem - choose 3 SAT or something similarly well understood. Then encode that 3sat problem into the paper’s solution domain.
If you get a password in polynomial time you are golden.
The contest approach wouldn’t necessarily hold rigor, because it doesn’t formally prove that all 2-MAXSAT problems can be solved using this algorithm. Just that one or more cherry-picked problems can. I think the paper really just needs to present actual proofs for the propositions it makes (as others have pointed out).
One of you is going to turn this into a puzzle and ask me in my next interview. I won't know the answer, but please don't laugh at me when you realize!
I could believe that an O(n^5) algorithm, like what was presented here, can satisfy P==NP, but still maintain the status quo where P!=NP for all practical problems. That is honestly what matters most of the time.
Still, there's almost certainly a mistake in this paper.
Though, P and NP are intrinsically defined asymptotically, so I'm not sure what it means for P != NP for all practical problems, other than saying that something like 80*n^5 is impractical to compute for n=10000, say.
When reducing one problem to another, you are allowed to have polynomial expansion in the problem size. If you are trying to take a practical problem and reducing it to MAX-2-SAT, you may have an n^2 or n^3 expansion. If you get lucky, the expansion may merely be a factor, like 2n or 5n. So now you're solving a problem that's at least O([big constant]*n^5), but could likely be O(n^10) or worse for any real problems.
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.
At n > 1000, exponential seems more of a problem. But 3SAT can apparently be reduced to MAX2SAT increasing the length by a factor 10, so that doesn't seem prohibitive to me.
I mean, the practical impact of this seems to be that the lower limit of where you can use a SAT solver or an LP solver to solve your problems increases by about a factor of 10 (or 100 at most). That's very useful, but still pretty small, and generally too small to really be useful on the hard problems that P = NP was "supposed" to crack. If this algorithm were able to be parallelized, that would be a different story.
Also, I assume most people would not go through 3SAT to MAX2SAT, they would just reduce directly there.
Not the person you're responding to, but that is one of the reasonable limitations of P=NP algorithm.
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.
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.
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 ?