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

51–60 of 106 posts

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

#51

Post by tromp »

Kranar wrote: post #46
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.

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.

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

#52

Post by [deleted] »

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…

[deleted]

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

#53

Post by tgflynn »

likpok wrote: post #50
tgflynn wrote: post #28

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

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

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.

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

#54

Post by klyrs »

js8 wrote: post #45
FartyMcFarter wrote: post #40

Earlier quoted context omitted.

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

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…

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.

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

#55

Post by remram »

tromp wrote: post #38
pcwalton wrote: post #32

Earlier quoted context omitted.

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

That's just not how keys work. If someone finds the key to my house and uses it to open the door and take something, it's still theft.

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

#56

Post by adgjlsfhk1 »

klyrs wrote: post #54
js8 wrote: post #45

Earlier quoted context omitted.

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…

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.

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

#57

Post by scythe »

kadoban wrote: post #29
scythe wrote: post #20

Earlier quoted context omitted.

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…

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

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

#58

Post by klyrs »

adgjlsfhk1 wrote: post #56
klyrs wrote: post #54

Earlier quoted context omitted.

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.

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

#59

Post by js8 »

klyrs wrote: post #54
js8 wrote: post #45

Earlier quoted context omitted.

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…

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

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

#60

Post by pfedak »

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.

Post reply on HN