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

71–80 of 106 posts

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

#71

Post by klyrs »

js8 wrote: post #59
klyrs wrote: post #54

Earlier quoted context omitted.

Nobody wants to read your draft about an algorithm that doesn't work. Your implementation is already giving you the critique that you need. If you get it to work and it's obviously polynomial time, you'll have something to talk about.

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…

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

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

#72

Post by Kranar »

tromp wrote: post #70
Kranar wrote: post #65

Earlier quoted context omitted.

It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP. NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete. Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution. NP, NP-Complete…

The decision problem for ECDLP { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve } is trivially in NP.

I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP.

With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to ECDLP is in P.

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

#73

Post by js8 »

klyrs wrote: post #71
js8 wrote: post #59

Earlier quoted context omitted.

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…

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

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?

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

#74

Post by theGnuMe »

js8 wrote: post #34

Well, this is somewhat heartbreaking for me. I haven't read the paper, but the result sounds very plausible to me. I am also an amateur working on P=NP. Last week, I think I also proved that P=NP, but with a different method, and was about to seek publication. My result seems very similar to his, yet very different. I can prove that class of SAT which is intersection of 2SAT and XORSAT is NP-complete by reduction to…

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

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

#75

Post by tgflynn »

Kranar wrote: post #72
tromp wrote: post #70

Earlier quoted context omitted.

The decision problem for ECDLP { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve } is trivially in NP.

I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP. With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to…

A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.

If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.

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

#76

Post by tromp »

Kranar wrote: post #72
tromp wrote: post #70

Earlier quoted context omitted.

The decision problem for ECDLP { (Curve_spec, P, x) : x is a prefix of the discrete log of point P on the specified elliptic curve } is trivially in NP.

I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP. With that said, even if the decision problem for ECDLP is in NP and P = NP, that does not mean that a solution to…

> ECDLP is assumed to be in a higher complexity class than DLP.

No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.

> With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P.

It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.

[1] https://en.wikipedia.org/wiki/Discrete_logarithm

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

#77

Post by adgjlsfhk1 »

js8 wrote: post #73
klyrs wrote: post #71

Earlier quoted context omitted.

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

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?

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

#78

Post by FartyMcFarter »

js8 wrote: post #73
klyrs wrote: post #71

Earlier quoted context omitted.

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

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?

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

#79

Post by karmakurtisaani »

Ah, but the question of P=NP has been already settled several times even, and as P!=NP too, see https://www.win.tue.nl/~wscor/woeginger/P-versus-NP.htm

(To the ones who did not waste their best years doing theoretical computer science, this was in jest - the paper most definitely contains mistakes)

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

#80

Post by js8 »

theGnuMe wrote: post #74
js8 wrote: post #34

Well, this is somewhat heartbreaking for me. I haven't read the paper, but the result sounds very plausible to me. I am also an amateur working on P=NP. Last week, I think I also proved that P=NP, but with a different method, and was about to seek publication. My result seems very similar to his, yet very different. I can prove that class of SAT which is intersection of 2SAT and XORSAT is NP-complete by reduction to…

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 everything stabilizes) can ever work, because it would contradict Razborov result on monotone circuits. I don't remember the exact argument, but I think it would imply a polynomial monotone circuit capable of resolving the instance. Also, XORSAT is not really amenable to this either, to solve arbitrary XORSAT instance you have to add together arbitrary number of linear equations, so the number of variables per equation can balloon up.

That's why more recently I focused on understanding what exactly is the role of XORSAT, and by serendipity, I stumbled upon the above-mentioned reduction (which I think is a really exciting result). XORSAT is great for testing different algorithms, because despite the fact we have a nice polynomial algorithm (Gaussian elimination), one can easily create arbitrary (and loopy) instances where propagation is difficult.

The way I see it, to avoid the problems with the bound, you need to preprocess the linear equations "inherent" in the instance by adding extra variables. The exact way to add variables depends on the instance, but it can be done by solving the linear equations. Propagation algorithms that go into the process blindly, without understanding the underlying linear structure, will mysteriously fail.

However, my current approach through logic, basically building up theorems about the instance, until it is decided, can be considered a generalization of the propagation approaches. The messages are true statements about variables, which are propagated by deduction rules of the logic. But this is done only after we have discerned the linear structure in the problem, which is addressed globally, as described above.

Post reply on HN