Hacker News Reader

Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

Still, the result is very interesting, since many problems can be solved asymptotically faster once subproblems that can be represented as 3-SAT can be solved faster. For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

> Moreover, it was already known that some NP-complete problems admit sub-exponential algorithms. For example, planar graph 3-colorability can be solved in 2^O(sqrt(n)) time. This is not only sub-exponential, but vastly better than the running time of the new 3-SAT algorithm.

I'm not real good at these sorts of details, but I'm struggling more than usual here. From what you say, and from things I think I know:

* Planar graph 3-colouring (P3COL) is NP-complete;

* Therefore 3-SAT can be reduced in polynomial time to P3COL;

* There is an algorithm for P3COL that runs in 2^O(sqrt(n)) time;

* Therefore there is an algorithm for 3-SAT that runs in 2^O(sqrt(n)).

That doesn't feel right ... where is the error?

Say the polynomial reduction is P(n)=n^2 then the algorithm for 3-SAT is 2^O(sqrt(P(n))) = 2^O(n)

Gotcha ... thank you.

Now I need to digest the implications of that, and I need to find the algorithm for P3COL.

I need a coffee ...

> For example, we now have now have a deterministic interger factoring algorithm with run time N^o(1), where N is the integer being factored. Heuristic algorithms already achieved this bound, but the new claim is a deterministic worst-case guarantee. The result is a fairly straightforward application of the new 3-SAT solver.

This can't be true unless you're talking about unfathomably large integers, since the new 3SAT algorithm only improves on the 2^n bound for n > 10^100000000. That is, it's not in any way a practical algorithm that will ever be runnable on any possible computer.

I'm reading O(1.3289^n) for 3-colorability.

> However, it would still be a mathematically extremely interesting result, as it would tell you that any problem where it is easy to verify if a solution is correct carries some hidden structure that makes it "easy" to generate the solutions.

Your ""easy"" here means actually hard, not easy at all, so I don't think this is any evidence that it would be "extremely interesting".

And that's actually a point of the article: some problem being solvable by a polynomial algorithm was originally only interesting insofar it was a proxy for being easy. We were interested in easy solvability, not polinomiality itself. But now the proxy has mutated into an optimization target.

Even though we started with an intention of characterizing what is easy and what is not, we have come to understand that P = NP would actually be an extremely interesting result, mathematically even if not for practical engineering.

The point would be that it would prove that any problem can be solved without exploring all possible solutions, at least for problems whose solutions can be verified in polynomial time. Even more startlingly, since any problem in NP can be reduced to a problem in NP-complete (including all of the problems in NP-complete), it would mean that there exists a single algorithm that can solve any problem in NP without having to explore the entire solution space.

This would be an extremely startling discovery, even if the algorithm for doing so would turn out to have galactic complexity and thus no practical applicability. It would probably lead to a vastly different understanding about how problem solving works, and might turn out to have much more wide implications, such as in physics, perhaps even shedding some new light on whether quantum computing is really fundamentally more efficient than classical computing (which in turn is a question that has profound implications on the ties between classical and quantum mechanics, likely touching on the measurement problem).

> Exponential complexity is what you automatically get when your algorithm is "generate a possible solution, verify if it's correct, repeat if it's not".

I might be misunderstanding you, but this surely depends on the size of the candidate set in the problem. For a problem like "determine whether a given list of integers of length `n` contains a pair that sum to 100" the naive brute-force algorithm is polynomial. If you replace "pair" by "subset" then the naive brute-force algorithm becomes exponential.

Yes, I should have been more careful with the wording. Some problems have polynomial numbers of possible solutions, so for those there is no discussion of this kind. The more important point is that for some problems with a more-than-polynomial solution space (since even exponential is not precise enough, the solution space can be more than polynomial, such as n! for traveling salesman) we still have polynomial solutions, whereas for others we do not know of such algorithms.

The question can actually be generalized further - is it the case that for any solvable problem it's possible to find a solution without verifying every possible solution, and more specifically, only a tiny subset of the solution space? This would apply even beyond P vs NP, the same question would arise for EXP vs NEXP (that is, problems where we can find a solution vs just verify a given solution in exponential time), and same for factorial or Ackerman or any other complexity we want to imagine.

Looking at the problem in this way should also make it easier to construct a more strictly practical version of P vs NP, though it actually gets much harder to pin down details. That is, we can construct complexity classes that better match "what is plausibly solvable with a real computer" vs "what is plausibly verifiable with a real computer" and ask a similar question: given any problem of the second kind, can there be any generic algorithm of the first kind that would solve it?

Maybe I'm reading a bit too much into it but knowing it is NP (i.e. can be verified in polynomial time by a Turing machine) means it can be solved in polynomial time by a nondeterministic turing machine and there's at worst 2^N branches in it. Sort of. Giving a naive expectation of 2^N runtime times some polynomial. Which is exponential.