Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The polynomial algorithm for 3-SAT problem (or P=NP)

romvf.wordpress.com

Post reply on HN
Print view View original

111–120 of 156 posts

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#111

Post by _delirium »

jchonphoenix wrote: post #53
tshaddox wrote: post #45

Earlier quoted context omitted.

To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to…

Actually, yes. Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. Additionally, P=NP suggests that NP in RP. If an inefficient deterministic algorithm in P is found, I'm sure a much faster randomized algorithm would soon follow.

> Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm.

This hasn't been the case in linear programming, at least: 30 years after it was proven to be in P, the old exponential algorithm (the simplex method) is still competitive with the best known polynomial algorithms (interior point methods). From a practical perspective, no real efficiency breakthrough. The fact that there are now two families of algorithms with good performance for the problem is an improvement, but the fact that one of them is theoretically polynomial doesn't seem to have led to dramatic speed gains.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#112

Post by DrJosiah »

mitko wrote: post #85

tl,dr version of his strategy (as far as I understood it) 1. For a fixed permutation construct a Viterbi-like search on the triplet assignments - if it fails it is not satisfiable. However, if it doesn't fail right away, there is still no guarantee there is an assignment. Call this structure compact triplet (CTF) or whatever. 2. Constuct a small set of permutation (at most m) for which every clause in the original CN…

That's more or less what I got out of it as well, though I came at it from the other direction...

If you skip the first part about pre-processing, and instead look at the graph that is generated, you can come up with following:

1. There exists a graph consisting of potential truth assignments on N unknowns in M clauses consisting of 7M nodes, and 2 edges.

2. Label each node uA,uB,uC,vA,vB,vC where u? is the unknown number, and v? is whether that unknown is true or false.

3. Edges exist between node I and node J if either nodes I and J share zero unknowns, OR both I and J share at least one variable AND all shared variables have the same value.

4. For there to be an assignment that causes the full statement to be correct, you must find an M-clique (a complete graph on M nodes within the 7M node graph).

Solving part 4 is NPC.

His claim is, basically, that if you permute/partition the input (to construct the tables), you can construct a disconnected graph with far fewer edges (get rid of the first part of #3 above), then add links graphs in such a way that if you can find a path from a tier-1 node to a tier-2 node, ..., to a tier-M node, examining the labels is sufficient to solve the problem. The two nasty parts are finding an efficient permutation/partition step, then managing to properly link the disconnected graphs. As you say, the two steps that the author hand-waves.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#113

Post by wnoise »

cperciva wrote: post #20

I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…

It's actually pretty easy to construct hard problems. A random 3-SAT problem is hard when it has the right density ratio of clauses to Boolean variables. Too few, and it's (relatively) easy to find a satisfying assignment. Too many, and it's easy to find a contradiction. This ratio is around 4.26, and it can actually be viewed as "thermodynamic" phase transition. In the large n limit, almost all 3-sat problems with a lower ratio are solvable, and almost all above that are not.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#115

Post by mzl »

_delirium wrote: post #111
jchonphoenix wrote: post #53

Earlier quoted context omitted.

Actually, yes. Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. Additionally, P=NP suggests that NP in RP. If an inefficient deterministic algorithm in P is found, I'm sure a much faster randomized algorithm would soon follow.

> Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm. This hasn't been the case in linear programming, at least: 30 years after it was proven to be in P, the old exponential algorithm (the simplex method) is still competitive with the best known polynomial algorithms (interior point methods). From a practical perspective, no r…

OTOH, simplex is very efficient already. Average-case complexity for random matrices is polynomial, and there are some interesting results that extend beyond that (see http://arxiv.org/abs/cs/0111050).

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#116

Post by wlievens »

_cbsz wrote: post #66
ezalor wrote: post #49

Earlier quoted context omitted.

The magic of the cloud! Imagine running that on Heroku (for instance): it would be costly (price) but possible.

Just parallelize your algorithm and use n^5 machines ;)

Is any polynomial algorithm parallelizable?

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#117

Post by wlievens »

phamilton wrote: post #5

I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"

Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements.

Though it's probably inaccurate, that's how I intuit the matter.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#118

Post by RiderOfGiraffes »

wnoise wrote: post #113
cperciva wrote: post #20

I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…

It's actually pretty easy to construct hard problems. A random 3-SAT problem is hard when it has the right density ratio of clauses to Boolean variables. Too few, and it's (relatively) easy to find a satisfying assignment. Too many, and it's easy to find a contradiction. This ratio is around 4.26, and it can actually be viewed as "thermodynamic" phase transition. In the large n limit, almost all 3-sat problems with a…

I'd be interested to see a reference for that result. I've been working for some time on the equivalent problem for graph 3-coloring, and really there are only some vague, heuristic results. I should think it also depends on the randomness model you use. In graph coloring some random processes give easy problems and others give hard problems for the same density.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#119

Post by sid0 »

dejb wrote: post #98
cperciva wrote: post #62

Earlier quoted context omitted.

Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.

True. However I don't think the article really implies that P = NP (although the title certainly does). From what I can see the article only addresses the class of NP-complete problems. Factoring is not known or believed to be NP-complete so it wouldn't directly prove that factoring was in P. Please correct me if I'm wrong. Edit : For some reason I can't reply to posts so I'll do it here. RiderOfGiraffes> It would wi…

From what I understand they a 'thought to be' the toughest but this isn't proven.

Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version).

So who is still standing as a contender for the hardest problem in NP?

If P = NP, then all problems in NP are as easy as each other, so this question is meaningless.

Re: The polynomial algorithm for 3-SAT problem (or P=NP)

#120

Post by sid0 »

wlievens wrote: post #117
phamilton wrote: post #5

I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"

Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements. Though it's probably inaccurate, that's how I intuit the matter.

Though it's probably inaccurate, that's how I intuit the matter.

It's actually quite accurate, but you can do even better: any other NP problem can be "compiled down" to one 3-SAT statement.

Post reply on HN