3 ms·

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

by js8 4y 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.

FartyMcFarter 4y 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.
- js8 4y ago
  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.
klyrs 4y 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.
- js8 4y ago
  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 4y ago
    If your reduction can solve factoring, what are the factors of 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199?
    - js8 4y ago
      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.
      - tgflynn 4y ago
        Why don't you try testing your algorithm on some 1000 variable or so SAT instances ? There are thousands of such problems that have been created for the SAT competitions. If your code can solve all of them and is really P-time then I think there are many people who would be interested in looking at your algorithm, myself included.

by js8 4y ago

FartyMcFarter 4y 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.

js8 4y ago
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.

klyrs 4y 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.

js8 4y ago
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 4y ago
  If your reduction can solve factoring, what are the factors of 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199?
  - js8 4y ago
    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.
    - tgflynn 4y ago
      Why don't you try testing your algorithm on some 1000 variable or so SAT instances ? There are thousands of such problems that have been created for the SAT competitions. If your code can solve all of them and is really P-time then I think there are many people who would be interested in looking at your algorithm, myself included.