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

31–40 of 106 posts

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

#31

Post by mabbo »

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.

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

#32

Post by pcwalton »

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.

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

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

#33

Post by MPSimmons »

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

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

#34

Post by js8 »

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

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

#35

Post by Strilanc »

hackcasual wrote: post #24
tromp wrote: post #16

Earlier quoted context omitted.

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

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

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

#36

Post by jojohohanon »

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.

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

#37

Post by Mizza »

mabbo wrote: post #31

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 harde…

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

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

#38

Post by tromp »

pcwalton wrote: post #32
tromp wrote: post #16

Earlier quoted context omitted.

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 cryptocurren…

> cryptocurrency theft is a crime

If you know the private key, then you own the coins.

At least that's the whole basis that crypto currency is founded on...

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

#39

Post by jcranmer »

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?

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.

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

#40

Post by FartyMcFarter »

js8 wrote: post #34

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…

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.

Post reply on HN