Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 2-MAXSAT Problem Can Be Solved in Polynomial Time

arxiv.org

Post reply on HN
Print view View original

21–30 of 106 posts

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#21

Post by vadiml »

pclmulqdq wrote: post #13
chriskanan wrote: post #8

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.

The author is CS professor in university of Winnipeg

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#22

Post by pclmulqdq »

tgv wrote: post #15
pclmulqdq wrote: post #7

Earlier quoted context omitted.

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.

How so? Impossibly large constants?

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.

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#23

Post by pclmulqdq »

vadiml wrote: post #21
pclmulqdq wrote: post #13

Earlier quoted context omitted.

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.

The author is CS professor in university of Winnipeg

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.

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#24

Post by hackcasual »

tromp wrote: post #16
Ono-Sendai wrote: post #6

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.

Only works if they have been moved. Addresses start out as hashes of ECC keys, not the keys themselves

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#25

Post by YeGoblynQueenne »

geophile wrote: post #2

P=NP alert

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

In any case, that someone says they proved P=NP is not such a big red flag as people seem to think.

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#26

Post by local_crmdgeon »

marcodiego wrote: post #19

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

Polynomial time can still be truly enormous

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#27

Post by CaptainNegative »

scythe wrote: post #20
Ono-Sendai wrote: post #6

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.

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.

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.

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#28

Post by tgflynn »

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 ?

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#29

Post by kadoban »

scythe wrote: post #20
Ono-Sendai wrote: post #6

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.

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.

Re: The 2-MAXSAT Problem Can Be Solved in Polynomial Time

#30

Post by dvdkhlng »

rlili wrote: post #12

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, , for example, it would be connected to , but not overlapped with . Being aware of this difference is important since the overlapped spans imply the consecutive ‘ ’s, just like and , which correspond to two consecutive…

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

Post reply on HN