13 ms·

The 2-MAXSAT Problem Can Be Solved in Polynomial Time

61 points by 9NRtKyP4 3y ago

geophile 3y ago
P=NP alert
- comfypotato 3y ago
  Which means something’s probably wrong with the proof, right?
  - utopcell 3y ago
    Of course.
  - sieste 3y ago
    A more fitting last sentence of the abstract would then be "But that would mean P=NP, so I must have made a mistake somewhere. Help!"
- pclmulqdq 3y ago
  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.
  - tgv 3y ago
    How so? Impossibly large constants?
    - pclmulqdq 3y ago
      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.
      - tgv 3y ago
        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.
        pclmulqdq 3y ago
        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.
    - jcranmer 3y ago
      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.
  - Vervious 3y ago
    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.
- YeGoblynQueenne 3y ago
  Donald Knuth thinks P=NP, but even if we find a proof it won't be as useful as we think: https://youtu.be/XDTOs8MgQfg https://youtu.be/XDTOs8MgQfg In any case, that someone says they proved P=NP is not such a big red flag as people seem to think.
erk__ 3y ago
Also discussed a tiny bit yesterday https://news.ycombinator.com/item?id=35712326 https://news.ycombinator.com/item?id=35712326
- noobermin 3y ago
  That's hardly a discussion. The reality is yes it's an arxiv paper and I'm not a computational complexity expert so I cannot gauge it for myself.
Ono-Sendai 3y ago
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.
- erk__ 3y ago
  If I read the paper correctly the 2-MAXSAT problem is usually referred to as MAX-2-SAT https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-satisfiability https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...
- tromp 3y ago
  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.
  - jmercan 3y ago
    There is an upper bound in the number of private keys available even if it isn't an issue in practice. You can target anyone's wallet in O(1) time, no proofs needed :^)
  - hackcasual 3y ago
    Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves
    - Strilanc 3y ago
      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".
chriskanan 3y ago
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.
- pclmulqdq 3y ago
  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.
  - vadiml 3y ago
    The author is CS professor in university of Winnipeg
    - pclmulqdq 3y ago
      He's the perfect profile for having the start of a P/NP proof: a full professor in computer science, but not really in the subfield of CS theory.
- rwmj 3y ago
  He seems pretty qualified if this page is accurate: https://ieeexplore.ieee.org/author/37087254612 https://ieeexplore.ieee.org/author/37087254612
deleted 3y ago
[deleted]
rlili 3y ago
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.
- sp332 3y ago
  If you put a \ in front of your * you can get the * to show up instead of italicizing. *Example*
- dvdkhlng 3y ago
  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. [1] https://arxiv.org/pdf/2304.12517.pdf https://arxiv.org/pdf/2304.12517.pdf
  - pfedak 3y ago
    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.
marcodiego 3y ago
"Hence, we provide a proof of P = NP." 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.
- local_crmdgeon 3y ago
  Polynomial time can still be truly enormous
tgflynn 3y ago
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 ?
- likpok 3y ago
  > 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.
  - tgflynn 3y ago
    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.
mabbo 3y ago
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.
- Mizza 3y ago
  All of this, but don't please don't bother Terry with crackpot P=NP ideas.
MPSimmons 3y ago
>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. Talk about burying the lede.
js8 3y ago
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).
- FartyMcFarter 3y ago
  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.
  - js8 3y ago
    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.
jojohohanon 3y ago
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.
- e79 3y ago
  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).
hota_mazi 3y ago
> Hence, we provide a proof of P = NP. Is this serious?
haliskerbas 3y ago
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!
pfedak 3y ago
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.
- BrejlaCZ 3y ago
  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...
- tgflynn 3y ago
  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.
rsrsrs86 3y ago
No proof inside?
karmakurtisaani 3y ago
Ah, but the question of P=NP has been already settled several times even, and as P!=NP too, see https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm (To the ones who did not waste their best years doing theoretical computer science, this was in jest - the paper most definitely contains mistakes)
deleted 3y ago
[deleted]

61 points by 9NRtKyP4 3y ago

geophile 3y ago

P=NP alert

comfypotato 3y ago
Which means something’s probably wrong with the proof, right?
- utopcell 3y ago
  Of course.
- sieste 3y ago
  A more fitting last sentence of the abstract would then be "But that would mean P=NP, so I must have made a mistake somewhere. Help!"
pclmulqdq 3y ago
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.
- tgv 3y ago
  How so? Impossibly large constants?
  - pclmulqdq 3y ago
    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.
    - tgv 3y ago
      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.
      - pclmulqdq 3y ago
        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.
  - jcranmer 3y ago
    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.
- Vervious 3y ago
  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.
YeGoblynQueenne 3y ago
Donald Knuth thinks P=NP, but even if we find a proof it won't be as useful as we think: https://youtu.be/XDTOs8MgQfg https://youtu.be/XDTOs8MgQfg In any case, that someone says they proved P=NP is not such a big red flag as people seem to think.

erk__ 3y ago

Also discussed a tiny bit yesterday https://news.ycombinator.com/item?id=35712326 https://news.ycombinator.com/item?id=35712326

noobermin 3y ago
That's hardly a discussion. The reality is yes it's an arxiv paper and I'm not a computational complexity expert so I cannot gauge it for myself.

Ono-Sendai 3y ago

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.

erk__ 3y ago
If I read the paper correctly the 2-MAXSAT problem is usually referred to as MAX-2-SAT https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-satisfiability https://en.wikipedia.org/wiki/2-satisfiability#Maximum-2-sat...
tromp 3y ago
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.
- jmercan 3y ago
  There is an upper bound in the number of private keys available even if it isn't an issue in practice. You can target anyone's wallet in O(1) time, no proofs needed :^)
- hackcasual 3y ago
  Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves
  - Strilanc 3y ago
    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".

chriskanan 3y ago

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.

pclmulqdq 3y ago
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.
- vadiml 3y ago
  The author is CS professor in university of Winnipeg
  - pclmulqdq 3y ago
    He's the perfect profile for having the start of a P/NP proof: a full professor in computer science, but not really in the subfield of CS theory.
rwmj 3y ago
He seems pretty qualified if this page is accurate: https://ieeexplore.ieee.org/author/37087254612 https://ieeexplore.ieee.org/author/37087254612

deleted 3y ago

[deleted]

rlili 3y ago

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.

sp332 3y ago
If you put a \ in front of your * you can get the * to show up instead of italicizing. *Example*
dvdkhlng 3y ago
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. [1] https://arxiv.org/pdf/2304.12517.pdf https://arxiv.org/pdf/2304.12517.pdf
- pfedak 3y ago
  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.

marcodiego 3y ago

"Hence, we provide a proof of P = NP." 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.

local_crmdgeon 3y ago
Polynomial time can still be truly enormous

tgflynn 3y ago

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 ?

likpok 3y ago
> 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.
- tgflynn 3y ago
  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.

mabbo 3y ago

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.

Mizza 3y ago
All of this, but don't please don't bother Terry with crackpot P=NP ideas.

MPSimmons 3y ago

>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. Talk about burying the lede.

js8 3y ago

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).

FartyMcFarter 3y ago
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.
- js8 3y ago
  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.

jojohohanon 3y ago

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.

e79 3y ago
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).

hota_mazi 3y ago

> Hence, we provide a proof of P = NP. Is this serious?

haliskerbas 3y ago

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!

pfedak 3y ago

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.

BrejlaCZ 3y ago
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...
tgflynn 3y ago
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.

rsrsrs86 3y ago

No proof inside?

karmakurtisaani 3y ago

Ah, but the question of P=NP has been already settled several times even, and as P!=NP too, see https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm (To the ones who did not waste their best years doing theoretical computer science, this was in jest - the paper most definitely contains mistakes)

deleted 3y ago

[deleted]