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

61–70 of 106 posts

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

#61

Post by FartyMcFarter »

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…

> somebody else will get the prize?

> Mathematics should be about collaborative understanding of the universe

If you really think mathematics should be about collaboration and not competition, why do you worry about who gets the prize?

You should pick what's more important to you - if it's collaboration, why not publish the steps you've accomplished? If someone else uses it to achieve a full solution, you'll still have a claim to part of the credit towards the solution.

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

#62

Post by adgjlsfhk1 »

klyrs wrote: post #58
adgjlsfhk1 wrote: post #56

Earlier quoted context omitted.

I don't think this is quite true. Most NP-hard problems are usually solvable in polynomial time, so your algorithm looking like it runs in polynomial time doesn't tell you much.

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.

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

#63

Post by pfedak »

dvdkhlng wrote: post #30
rlili wrote: post #12

For me, the following is a bit that seems particularly prone to be invalidated, even more so considering that the author doesn't present any proof of it: > Here, we notice that if we had one more span, , for example, it would be connected to , but not overlapped with . Being aware of this difference is important since the overlapped spans imply the consecutive ‘ ’s, just like and , which correspond to two consecutive…

I already have problems following Proposition 1 where they introduce a different DNF with twice the clauses of the original CNF than claim that maximizing the satisfied clauses in the DNF would also yield a maximum satisfied solution for the CNF. It's a pitty they don't release any source code that we can unit-test against problems with known solutions (while also profiling run-time to stay within polynomial bounds)…

The conversion to DNF is fine. The original clauses map directly to pairs of new clauses, so fixing an assignment to the original variables V you can always satisfy the same number of the DNF clauses. You can do worse by choosing the wrong values for X, sure, but there's always a straightforward correspondence.

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

#64

Post by js8 »

FartyMcFarter wrote: post #61
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…

> somebody else will get the prize? > Mathematics should be about collaborative understanding of the universe If you really think mathematics should be about collaboration and not competition, why do you worry about who gets the prize? You should pick what's more important to you - if it's collaboration, why not publish the steps you've accomplished? If someone else uses it to achieve a full solution, you'll still ha…

Because I am also a human. I think I could still use the money (if anything, very few people want to be principled idiots who refuse $1m), and if I spent several years determined to understand it, perhaps it's worth spending some more to understand it fully. As I explained, it creates an atmosphere that prevents collaboration - it's incredibly hard to find anyone to talk about the problem with. Anyway, I am writing about my approach here, and I am about to write about it more. Still, people dismiss it outright.

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

#65

Post by Kranar »

tromp wrote: post #51
Kranar wrote: post #46

Earlier quoted context omitted.

The decision problem for ECDLP is not known to be NP-complete, in fact it's likely not NP-complete but rather NP-hard and therefore proving that P = NP would not provide any insight into finding a polynomial time solution for it.

Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.

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, NP-Hard etc... only refer to decision problems, not to general purpose computations.

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

#66

Post by js8 »

klyrs wrote: post #58
adgjlsfhk1 wrote: post #56

Earlier quoted context omitted.

I don't think this is quite true. Most NP-hard problems are usually solvable in polynomial time, so your algorithm looking like it runs in polynomial time doesn't tell you much.

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.

As already mentioned, it's not always that simple. For example, my current approach (modeled after Krom, who doesn't even have a Wikipedia page - no wonder nobody reads him!) is a more systematic search for a polynomial algorithm - construct a polynomial sized-logic in which theories have models that are satisfying instances of SAT, and prove its refutable-completeness. This proves existence of a polynomial algorithm, because you can generate all formulas of theory (coming from SAT instance) in said logic, and if you don't find a contradiction, the instance is satisfiable. The algorithm is kinda implicit, non-deterministic, if you will (because you can generate all the formulas in any order or even generate just a subset).

Anyway, my main point is - people beware, practically solvable P=NP (even for hard instances) is a very real possibility.

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

#67

Post by tgv »

pclmulqdq wrote: post #22
tgv wrote: post #15

Earlier quoted context omitted.

How so? Impossibly large constants?

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.

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

#68

Post by kadoban »

scythe wrote: post #57
kadoban wrote: post #29

Earlier quoted context omitted.

Technically (and depending on the problem, practically), giving large instances isn't a good test. For some problems, you can pick easy instances (even if large), or there can be ways to go backwards and generate an instance you know the answer to (prime factorization comes to mind). I believe that there's problems where it's difficult to even find a hard instance, it's just also difficult to prove that no difficult…

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

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

#70

Post by tromp »

Kranar wrote: post #65
tromp wrote: post #51

Earlier quoted context omitted.

Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.

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.
Post reply on HN