3 ms·

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

by 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.
    - js8 4y ago
      That's what I am generally doing and planning to do, however right now, the theory had priority (there is still couple weak spots in my proof which I need to patch up). But I will return to testing once I will have a better idea what I want the algorithm to do (as I mentioned, a more naive version of the method that combined solving 2-SAT and XORSAT failed with a bug, which I think I now understand). I think testing O(n^8) algorithm is pointless, so it needs more polishing (naive algorithm for 2-SAT (that follows from Krom) is O(n^3) or so, but the best methods are linear; so I feel there is a lot of room for improvement, but obviously my method is a little bit more complicated than 2-SAT, which it generalizes).
      - tgflynn 4y ago
        There's one thing I'd like to get some clarification on. You said in an earlier comment: > I am reducing to 2XSAT, which is a name for instances that are intersections of 2-SAT and XORSAT instances. It seems to me that 2-SAT and XORSAT are distinct problems. I mean there is no problem instance that is simultaneously a 2-SAT problem and an XORSAT problem instance. So how can there be instances that are intersections of both ?
        js8 4y ago
        The 2XSAT has clauses that are from 2-SAT or XORSAT. So it's a generalization of both. The solutions (boolean variable assignments) must satisfy both 2-SAT and XORSAT part of the problem, hence the solutions of the 2XSAT instance is their intersection. There are in fact problems that are both 2-SAT and XORSAT, but they seem to be rather trivial - those are linear equations that have up to 2 variables per equation. But that's not what I am talking about. I understand why people are confused with my off-hand comments, but I didn't plan to explain my approach here in detail, and I typed the first couple of comments when I was at work on my phone, where being precise is tedious.
FartyMcFarter 4y ago
The intersection of two sets is a subset of both sets. So that means you're reducing to 2SAT?
- js8 4y ago
  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.
  - klyrs 4y ago
    That isn't the intersection of 2SAT and XORSAT, it's the union. Problems in the intersection would be solvable by either type of solver. I don't think it's "obvious" that your problem class should be polynomial; 2XSAT as you've described it (is it your own invention? I haven't found a reference) appears to be a strictly more powerful problem class.
    - js8 4y ago
      It's not a union of those classes, it's a different class, and as you say, it's more powerful, because it can be projected (my reduction adds additional variables) into 3-SAT and SAT instance. Yes, 2XSAT is the name I gave it, and I couldn't find it anywhere. The reduction is surprisingly simple, yet nobody mentions it. That's why I am warning people here - just based on this alone, I 80% believe that P=NP with a practical algorithm (which either way involves solving linear equations). And I wouldn't be surprised somebody coming up with the algorithm. The reason why I say it's an intersection is because that's how the set of solutions of an instance looks like. That's what we need to figure out - how to characterize the sets of solutions described by SAT instance (i.e. sets of assignments to boolean variables that satisfy the instance). However, it's not that easy, even if you characterize them as interesections of 2-SAT and XORSAT instances, set of solutions to 2-SAT is notoriously hard to characterize too, for example, #2SAT is not known. And polynomial algorithms for 2-SAT and XORSAT are doing very different things, and it's not at all obvious how to generalize them into a common algorithm that can do both.

by js8 4y ago

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.
  - js8 4y ago
    That's what I am generally doing and planning to do, however right now, the theory had priority (there is still couple weak spots in my proof which I need to patch up). But I will return to testing once I will have a better idea what I want the algorithm to do (as I mentioned, a more naive version of the method that combined solving 2-SAT and XORSAT failed with a bug, which I think I now understand). I think testing O(n^8) algorithm is pointless, so it needs more polishing (naive algorithm for 2-SAT (that follows from Krom) is O(n^3) or so, but the best methods are linear; so I feel there is a lot of room for improvement, but obviously my method is a little bit more complicated than 2-SAT, which it generalizes).
    - tgflynn 4y ago
      There's one thing I'd like to get some clarification on. You said in an earlier comment: > I am reducing to 2XSAT, which is a name for instances that are intersections of 2-SAT and XORSAT instances. It seems to me that 2-SAT and XORSAT are distinct problems. I mean there is no problem instance that is simultaneously a 2-SAT problem and an XORSAT problem instance. So how can there be instances that are intersections of both ?
      - js8 4y ago
        The 2XSAT has clauses that are from 2-SAT or XORSAT. So it's a generalization of both. The solutions (boolean variable assignments) must satisfy both 2-SAT and XORSAT part of the problem, hence the solutions of the 2XSAT instance is their intersection. There are in fact problems that are both 2-SAT and XORSAT, but they seem to be rather trivial - those are linear equations that have up to 2 variables per equation. But that's not what I am talking about. I understand why people are confused with my off-hand comments, but I didn't plan to explain my approach here in detail, and I typed the first couple of comments when I was at work on my phone, where being precise is tedious.

FartyMcFarter 4y ago

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

js8 4y ago
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.
- klyrs 4y ago
  That isn't the intersection of 2SAT and XORSAT, it's the union. Problems in the intersection would be solvable by either type of solver. I don't think it's "obvious" that your problem class should be polynomial; 2XSAT as you've described it (is it your own invention? I haven't found a reference) appears to be a strictly more powerful problem class.
  - js8 4y ago
    It's not a union of those classes, it's a different class, and as you say, it's more powerful, because it can be projected (my reduction adds additional variables) into 3-SAT and SAT instance. Yes, 2XSAT is the name I gave it, and I couldn't find it anywhere. The reduction is surprisingly simple, yet nobody mentions it. That's why I am warning people here - just based on this alone, I 80% believe that P=NP with a practical algorithm (which either way involves solving linear equations). And I wouldn't be surprised somebody coming up with the algorithm. The reason why I say it's an intersection is because that's how the set of solutions of an instance looks like. That's what we need to figure out - how to characterize the sets of solutions described by SAT instance (i.e. sets of assignments to boolean variables that satisfy the instance). However, it's not that easy, even if you characterize them as interesections of 2-SAT and XORSAT instances, set of solutions to 2-SAT is notoriously hard to characterize too, for example, #2SAT is not known. And polynomial algorithms for 2-SAT and XORSAT are doing very different things, and it's not at all obvious how to generalize them into a common algorithm that can do both.