undefined | Better HN

0 pointsjs82y ago0 comments

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.

0 comments

klyrs2y ago

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.

adgjlsfhk12y ago

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.

klyrs2y ago

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.

2 more replies

js8OP2y ago

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.

klyrs2y ago

> I have both theoretically and practically verified the 2XSAT reduction, and I believe it's a step towards P=NP.

NP is generally thought to be harder than factoring, so I'm not sure that your reduction is a "reduction" in the sense that you've restated factoring in a (potentially-)harder-than-native problem space. Proving that factoring is polynomial would be a huge result indeed, but if your strategy requires you to prove P=NP along the way, you're focused on the wrong problem and I wouldn't expect you to get much traction.

1 more reply

FartyMcFarter2y ago

> somebody else will get the prize?

> Mathematics should be about collaborative understanding of the universe

If you really think mathematics should be about collaboration and not competition, why do you worry about who gets the prize?

You should pick what's more important to you - if it's collaboration, why not publish the steps you've accomplished? If someone else uses it to achieve a full solution, you'll still have a claim to part of the credit towards the solution.

1 more reply

j / k navigate · click thread line to collapse

0 pointsjs82y ago0 comments

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

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.

0 comments

klyrs2y ago

adgjlsfhk12y ago

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.

klyrs2y ago

2 more replies

js8OP2y ago

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?

klyrs2y ago

> I have both theoretically and practically verified the 2XSAT reduction, and I believe it's a step towards P=NP.

1 more reply

FartyMcFarter2y ago

> somebody else will get the prize?

> Mathematics should be about collaborative understanding of the universe

If you really think mathematics should be about collaboration and not competition, why do you worry about who gets the prize?

1 more reply

j / k navigate · click thread line to collapse