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

41–50 of 106 posts

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

#41

Post by tromp »

Strilanc wrote: post #35
hackcasual wrote: post #24

Earlier quoted context omitted.

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

Besides, Satoshi's coins are P2PK (Pay to Public Key), not P2PKH (Pay to Public Key Hash), so the point is moot.

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

#43

Post by e79 »

jojohohanon wrote: post #36

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

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

#45

Post by js8 »

FartyMcFarter wrote: post #40
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.…

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.

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

#46

Post by Kranar »

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.

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.

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

#47

Post by xorvoid »

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

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.

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

#48

Post by rwmj »

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.

He seems pretty qualified if this page is accurate: https://ieeexplore.ieee.org/author/37087254612

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

#49

Post by bagels »

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 is not how the law works. It's equivalent to knowing your bank account number and routing number and making an unauthorized transaction.

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

#50

Post by likpok »

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

Post reply on HN