[firechickenbird]

Interesting informal summarization of SAT. However, there is no such thing as "the hardest" NP-complete problem. By definition of NP-completeness, if you solve ANY NP-complete problem in polynomial time, you can solve every other NP-complete problem in polynomial time, thus they have equivalent difficulty (although, some problems may seem intuitively easier than others).

[Strilanc]

That's only true if you focus purely on the cost as being polynomial or not. The constant factors, the exponents, and the ability to represent difficult problems compactly, can of course differ pretty substantially. The ability to find approximate solutions, and the difficulty of the average case, can also differ substantially from problem to problem. An example of an application where these kinds of details are crucial is cryptography.

[Avshalom]

I think that was a slightly odd way of mentioning https://en.m.wikipedia.org/wiki/NP-hardness

[Hendrikto]

That is not entirely true. If you compare two implementations of bubble sort, they will both be O(n^2). Yet one can still be much more efficient than the other.

x^4 and x^10 are both polynomials.

[firechickenbird]

> That is not entirely true

what are you referring to?

Obviously x^4 != x^10, but noone has ever proven that "if SAT is P, then it would have the lowest (or highest) polynomial complexity among the other problems", or anything similar

[Hendrikto]

I was referring to this:

> [All NP-hard problems] have equivalent difficulty.

I get what OP meant, but there can still be some NP-hard problems that are more difficult than others.

As I said, x^4 and x^10 are both polynomials. I wouldn‘t call them "equivalent" though.

[hinkley]

Last time I looked at NP complete problems people were telling me to use SAT-family algorithms to solve them, so I’m quite confused at the moment.

[firechickenbird]

Let me first try to briefly summarize NP-completeness:

A problem A is NP-complete if:

- you can verify it's solution in polynomial time

- you can reduce it to any other NP-complete problem in polynomial time

Since polynomial reduction is transitive, the second point is equivalent to saying that "you can reduce it to SAT in polynomial time".

The reduction is simply a function that compiles the starting problem to SAT and preserves it's solvability (in a bijective way). In other words, to prove that a problem is NP-compelte, you must write a compilation function to SAT and also prove that every solution to the starting problem is also a solution to the destination problem in SAT. Furthermore you must also prove that any solution in the SAT version can be "decompiled" to a proper solution in the starting problem, so this is where the equivalence comes from and it's the reason that SAT is not really anyhow harder than other NP-complete problems.

The thing is, SAT has been heavily researched, so that's why you have extremely efficient SAT-solvers. So if you want to solve an NP-complete problem, you can simply compile it to SAT, solve it with well-known SAT-solvers and "decompile" the solution to your starting problem

[matklad]

The other way around: to prove that X is NP-complete you need to reduce SAT(or any other known NP complete problem) to X.

The intuition here is that if you have a magic algorithm which solves X efficiently, you should be able to use this algorithm to solve any other NP problem, like SAT.