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

81–90 of 106 posts

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

#81

Post by js8 »

adgjlsfhk1 wrote: post #77
js8 wrote: post #73

Earlier quoted context omitted.

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?

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

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.

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

#83

Post by js8 »

FartyMcFarter wrote: post #78
js8 wrote: post #73

Earlier quoted context omitted.

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?

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

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.

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

#84

Post by theGnuMe »

js8 wrote: post #80
theGnuMe wrote: post #74

Earlier quoted context omitted.

What's your take on survey propagation? I would think that any P=NP proof would take that into account or be similar.

I haven't really studied it in detail, but my motivation is similar, I see SAT as a simplified version of the marginal problem, and I want to solve marginal problem (or at least approximate) because I am interested in representing knowledge intensionally. I played with propagation a lot in the past, but I don't think local propagation (that resolves conditions of a bounded number of variables at a time, until everyth…

That jives with my intuition. I had forgotten about the connection between Gaussian elimination and xor sat. That does sound like a good direction to reason from.

How do you prevent an exponential increase in linear terms though?

Good luck!

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

#85

Post by tgflynn »

js8 wrote: post #81
adgjlsfhk1 wrote: post #77

Earlier quoted context omitted.

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

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 th…

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.

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

#86

Post by js8 »

tgflynn wrote: post #85
js8 wrote: post #81

Earlier quoted context omitted.

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 th…

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.

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

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

#87

Post by js8 »

theGnuMe wrote: post #84
js8 wrote: post #80

Earlier quoted context omitted.

I haven't really studied it in detail, but my motivation is similar, I see SAT as a simplified version of the marginal problem, and I want to solve marginal problem (or at least approximate) because I am interested in representing knowledge intensionally. I played with propagation a lot in the past, but I don't think local propagation (that resolves conditions of a bounded number of variables at a time, until everyth…

That jives with my intuition. I had forgotten about the connection between Gaussian elimination and xor sat. That does sound like a good direction to reason from. How do you prevent an exponential increase in linear terms though? Good luck!

I am still not sure about the exact role of Gaussian elimination. I thought that it will be somehow necessary, but it seems that if you only break linear equations to 3 variables per equation (by adding extra variables), you can get away without it. Although it certainly doesn't hurt to do it, I think for efficient algorithms, it will be required (and so the whole endeavor will be at least O(n^3)).

To prevent exponential increase in linear terms, I work within a sort of limited logic that only allows formulas that are ORs of (implications between) two linear equations of up to 2 variables. This logic accommodates both 2-SAT clauses and linear clauses of 3 variables, and seems to be able to emulate Gaussian elimination to some extent, but I am not yet completely sure how. Last week, I think I was able to generalize Krom's proof of refutable-completeness for 2-SAT logic (that has linear equations on 1 variable) to this logic, but I am in the process of double checking my result for gotchas like this.

There are other ideas how to control the linear terms, once you have the linear equations solved, it's easy to verify whether some variables are linearly dependent, because you have the basis, and modify the ordinary 2-SAT algorithm accordingly (2-SAT works by propagation via transitive dependency of literals, but if the 3 variables involved are linearly dependent, then you can derive lot more). These are mainly ideas how to make the polynomial algorithm even more efficient.

And thanks for encouragement!

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

#88

Post by pclmulqdq »

tgv wrote: post #67
pclmulqdq wrote: post #22

Earlier quoted context omitted.

When reducing one problem to another, you are allowed to have polynomial expansion in the problem size. If you are trying to take a practical problem and reducing it to MAX-2-SAT, you may have an n^2 or n^3 expansion. If you get lucky, the expansion may merely be a factor, like 2n or 5n. So now you're solving a problem that's at least O([big constant]*n^5), but could likely be O(n^10) or worse for any real problems.…

At n > 1000, exponential seems more of a problem. But 3SAT can apparently be reduced to MAX2SAT increasing the length by a factor 10, so that doesn't seem prohibitive to me.

I mean, the practical impact of this seems to be that the lower limit of where you can use a SAT solver or an LP solver to solve your problems increases by about a factor of 10 (or 100 at most). That's very useful, but still pretty small, and generally too small to really be useful on the hard problems that P = NP was "supposed" to crack. If this algorithm were able to be parallelized, that would be a different story.

Also, I assume most people would not go through 3SAT to MAX2SAT, they would just reduce directly there.

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

#89

Post by tgflynn »

js8 wrote: post #86
tgflynn wrote: post #85

Earlier quoted context omitted.

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.

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…

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 ?

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

#90

Post by tgflynn »

pfedak wrote: post #60

Unsurprisingly, there's nothing here. Most of the paper describes a brute force search across all possible variable assignments in the form of a graph (with some pointless polynomial improvements like making it a trie), where you build a path of vertices representing each set of truth values that satisfies a given expression. This clearly has exponential size, which the author alludes to in the "improvements" section…

I'm stuck in the III.A "Main Idea" section where he says:

> Doing this enables us to represent each Di as a variable sequence, but with all the negative literals being removed. See Table I for illustration.

What justification does he have for throwing out negated variables ? If you do that the problem likely becomes trivial, but has nothing to do with the original problem.

Post reply on HN