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

91–100 of 106 posts

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

#91

Post by klyrs »

js8 wrote: post #83
FartyMcFarter wrote: post #78

Earlier quoted context omitted.

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.

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.

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

#92

Post by pfedak »

tgflynn wrote: post #90
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.

I had trouble with that too initially. I think that's actually fine: the representation the paper wants to use is that the variables in a path are the ones set to true, so omitting one means that variable must be false to satisfy the expression.

It does create issues with determining which expressions are satisfied, since two different paths can meet at a merged trie vertex higher up, which requires the extra bookkeeping that kills it.

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

#93

Post by klyrs »

adgjlsfhk1 wrote: post #62
klyrs wrote: post #58

Earlier quoted context omitted.

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.

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.

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.

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

#94

Post by tgflynn »

pfedak wrote: post #92
tgflynn wrote: post #90

Earlier quoted context omitted.

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.

I had trouble with that too initially. I think that's actually fine: the representation the paper wants to use is that the variables in a path are the ones set to true, so omitting one means that variable must be false to satisfy the expression. It does create issues with determining which expressions are satisfied, since two different paths can meet at a merged trie vertex higher up, which requires the extra bookkee…

Ah, OK thanks, that definitely could have been more clearly explained.

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

#95

Post by js8 »

klyrs wrote: post #91
js8 wrote: post #83

Earlier quoted context omitted.

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.

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.

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.

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

#96

Post by js8 »

tgflynn wrote: post #89
js8 wrote: post #86

Earlier quoted context omitted.

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

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.

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

#97

Post by klyrs »

js8 wrote: post #95
klyrs wrote: post #91

Earlier quoted context omitted.

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.

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

As a mathematician, my advice to you is to build up some theory around this problem class. I find it entirely plausible that you can reduce 3sat to it. I'd encourage you to look for a reduction from 2XSAT to 3sat. Find some problems that are well-expressed in the language of 2XSAT. You might find something worthy of publication. From there you'll want to shop your results around at conferences. You may drum up some interest in your work, or even a collaborator. Just don't act confident that you've cracked a keystone problem in the field. You think you're on the right path, and that's exciting, but we've all been there and we've all met dozens of novices who were utterly convinced of their incorrect solution to this problem. It's a huge red flag that you're a waste of time.

As a grad student, I got perhaps hundreds of "dear professor" emails claiming proof of everything from squaring the circle to the BSD conjecture. Reflexively running from anybody making such claims is a necessary survival skill. Math is a field where the bullshit asymmetry principle[1] is particularly stark. Finding a flaw in a proof can take vastly more effort than is spent concocting it.

[1] https://en.m.wikipedia.org/wiki/Brandolini%27s_law

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

#98

Post by jmercan »

tromp wrote: post #16
Ono-Sendai wrote: post #6

Since the paper claims to give an algorithm for solving an NP-hard problem, e.g. it's a constructive proof, not just an existence proof, then presumably the author should be able to reduce some other problems to this one (2-Maxsat) and solve them as a demonstration.

I'd be more inclined to believe their P=NP claim if they used it to grab all of Satoshi's bitcoins. That should be the first order of business for anyone finding an efficient algorithm for the ECDLP (Elliptic Curve Discrete Log Problem), as implied by their constructive proof.

There is an upper bound in the number of private keys available even if it isn't an issue in practice.

You can target anyone's wallet in O(1) time, no proofs needed :^)

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

#99

Post by js8 »

klyrs wrote: post #97
js8 wrote: post #95

Earlier quoted context omitted.

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

As a mathematician, my advice to you is to build up some theory around this problem class. I find it entirely plausible that you can reduce 3sat to it. I'd encourage you to look for a reduction from 2XSAT to 3sat. Find some problems that are well-expressed in the language of 2XSAT. You might find something worthy of publication. From there you'll want to shop your results around at conferences. You may drum up some i…

The opposite reduction from 2XSAT to SAT is obvious, it's just a special case.

I think professionals of every field have to deal with passionate amateurs of all levels. I understand why many people don't want to do it, but IMHO overemphasis on professionalism (culturally coming from enormous peer pressures) is hurting any field. The superprizes make it even worse.

> Just don't act confident that you've cracked a keystone problem in the field.

I am not acting like that, but I also have to be honest that my goal is specific - to understand why we can or can't have a polynomial algorithm. I.e. I have a strategy already, what I need is a 2nd opinion about some specifics of it.

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

#100

Post by FartyMcFarter »

kadoban wrote: post #68
scythe wrote: post #57

Earlier quoted context omitted.

>I believe that there's problems where it's difficult to even find a hard instance Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter. It follows that it isn't any more difficult to construct a hard instance of any NP-hard problem than it is to encode a more easily constructible problem into the same. As for verifying the solution, th…

> Sure, but encoding the factorization of a large prime into 2-MAXSAT would necessarily imply constructing a hard instance of the latter. That should work if you pick something like one of the unsolved RSA challenges or something.

The RSA challenges are very easy to generate - just generate large random numbers, check if they pass a primality test like Miller-Rabin (this doesn't take long even with a naive implementation). Then multiply two of those that do pass the test (distinct ones!), and you're done.
Post reply on HN