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

101–106 of 106 posts

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

#101

Post by plpnpplpnp »

js8 wrote: post #99
klyrs wrote: post #97

Earlier quoted context omitted.

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

Honestly, I don't think you have the proof. Proving p is euqal to np will have very big consequences, not only in computer science but also in logics for example. I think this problem is far more complex than you think and it is not going to be solved by chance by an amateur. If it's going to be solved, there will be a deep math argument.

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

#102

Post by klyrs »

js8 wrote: post #99
klyrs wrote: post #97

Earlier quoted context omitted.

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

> my goal is specific - to understand why we can or can't have a polynomial algorithm

This is the entire question of P vs NP. I'd love to point you to a reference, but the question remains unresolved. Good hunting.

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

#103

Post by kadoban »

FartyMcFarter wrote: post #100
kadoban wrote: post #68

Earlier quoted context omitted.

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

Sure, but presumably they're difficult to solve. I'm saying that if they can _solve_ an unsolved one using this algorithm, that would certainly be compelling.

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

#104

Post by undreren »

tgflynn wrote: post #53
likpok wrote: post #50

Earlier quoted context omitted.

> So far I've only read the introduction and it doesn't obviously involve any advanced mathematics that I'm unfamiliar with so I could perhaps attempt an implementation. This is a bad sign for the paper. The prior cases of solving big foundational problems I'm aware of all introduce substantial new math. So much so that the actual problem is something of an afterthought. Wiles's proof of Fermat's last theorem is subs…

That's the kind of argument I've never put much credence in, otherwise I never would have even attempted to solve the problem. I still think it's possible that there could be a relatively simple solution that has so far eluded humans. They are burdened by many individual, institutional and societal biases and I think they are far less intelligent than they generally believe.

Simple proofs are often only possible, because the language of mathematics become increasingly descriptive over time.

The language conveniently helps us make incredibly complicated statements by using specialized terms. Simple solution are rarely that simple, once we eschew the jargon of the field.

We stand on the shoulders of giants, and all that.

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

#105

Post by BrejlaCZ »

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 haven't really understood how the proposed simplification should work... It's clearly exponential without it, but I am not sure about the supposed added labels. What should those be, conjunction and group subsets? Does that make them exponential?

The proofs and even explanations in this paper aren't very clear to me...

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

#106

Post by FartyMcFarter »

kadoban wrote: post #103
FartyMcFarter wrote: post #100

Earlier quoted context omitted.

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.

Sure, but presumably they're difficult to solve. I'm saying that if they can _solve_ an unsolved one using this algorithm, that would certainly be compelling.

Right - to elaborate, my point was that since:

1- it's easy to generate RSA-like challenges for factoring, a product of two large primes.

2- it's easy to turn these RSA-like challenges into instances of the SAT problem (the canonical NP-complete problem).

3- SAT problems can be reduced to any NP-complete problem.

4- these reductions are known, because the typical proof of NP-completeness is to provide a reduction from another NP-complete problem, which will ultimately end up with SAT if you follow the chain for long enough.

... it follows that it's not too hard to generate hard instances of any NP-complete problem, assuming that factoring itself is a hard problem.

Post reply on HN