[js8]

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.

[klyrs]

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.

[adgjlsfhk1]

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.

[klyrs]

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.

[js8]

As <cat-over-keyboard> already mentioned, it's not always that simple. For example, my current approach (modeled after Krom, who doesn't even have a Wikipedia page - no wonder nobody reads him!) is a more systematic search for a polynomial algorithm - construct a polynomial sized-logic in which theories have models that are satisfying instances of SAT, and prove its refutable-completeness. This proves existence of a polynomial algorithm, because you can generate all formulas of theory (coming from SAT instance) in said logic, and if you don't find a contradiction, the instance is satisfiable. The algorithm is kinda implicit, non-deterministic, if you will (because you can generate all the formulas in any order or even generate just a subset).

Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.

[adgjlsfhk1]

Sure, but most complicated polynomial time algorithms don't work like this. You either have cases like AKS which are obviously polynomial but not obviously correct, or cases that are obviously correct but not obviously polynomial.

[klyrs]

Algorithms which are obviously polynomial, and non-obviously correct are the only ones I'd entertain from a novice. It's not hard to mine for counterexamples, as long as the code runs.

[js8]

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.

[klyrs]

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

[js8]

No, I am not reducing to factoring, I only tested some on it because it's a relatively easy way to get hard instances.

I am reducing to 2XSAT, which is a name for instances that are intersections of 2-SAT and XORSAT instances.

Both 2-SAT and XORSAT have polynomial algorithms, why is it hard to believe that their intersection has one too?

[adgjlsfhk1]

If your reduction can solve factoring, what are the factors of 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199?

[js8]

I already said, I don't have an efficient algorithm. Once I will have, in my estimation, at best, it will be O(n^3) (n is number of variables), which still means a lot - to factor 16-bit integer, my (linear) 2XSAT reduction requires about 4000 variables, so the number of variables for a cryptographically-strong problem will be in millions. You need to have a very efficient parallel algorithm to deal with that, and that's very low on the list of priorities - first I need to understand how to actually make the algorithm efficient (so far I think I proved there is a polynomial bound - around O(n^8) or so, but I know for sure it's very inefficient, because I am doing it very naively).

There are other ways to improve the method, which (if indeed P=NP) are incredibly interesting - you can directly compose presolved general instances and specialize on them. Kinda like if you need to compute many solutions to linear equations, you only need to factor the matrix once.

[FartyMcFarter]

The intersection of two sets is a subset of both sets. So that means you're reducing to 2SAT?

[js8]

No, you misunderstand, the intersection is in the solution to the instance. The 2XSAT are problems that can contain both 2-SAT clauses (two literals per OR clause) and XORSAT clauses (linear equations). 2-SAT (as well as XORSAT) are just special cases of that. You can also think of it as 2-SAT, but confined into a linear subspace of Z_2^n.

[FartyMcFarter]

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

[js8]

Because I am also a human. I think I could still use the money (if anything, very few people want to be principled idiots who refuse $1m), and if I spent several years determined to understand it, perhaps it's worth spending some more to understand it fully. As I explained, it creates an atmosphere that prevents collaboration - it's incredibly hard to find anyone to talk about the problem with. Anyway, I am writing about my approach here, and I am about to write about it more. Still, people dismiss it outright.