Flying Pigs Unsafe at Any Speed

Take a moment and imagine a flying pig. Do you see a pig with tiny wings lazily guiding along. But pigs are not particularly slow animals as anyone has seen a pig race at a county fair can attest to that. So why not in the air shouldn't a pig go faster than an unladen African swallow?

I have a point discussing the fastness of a flying pig. Consider my favorite flying pig, P = NP. I would put more probability on an actual flying pig (thanks CRISPR) than polynomial-time algorithms for traveling salesman.

Sometimes I get in the following conversation:

AI person: The P v NP problem is irrelevant as we have machine learning and SAT solvers and we can for all practical purposes solve NP-complete problems.
Me: If P = NP we can solve AI!
AI: If P = NP it's likely to have a very slow poly-time algorithm with high exponents and constants and be for all practical purposes useless.

Let's break that down. The claim is E(running time of SAT|running time of SAT is poly) = cn^k for some large c and k. First of all you are conditioning on a probability zero event. Beyond that nearly all the known problems we know that sit in polynomial time have practical efficient solutions. So under the assumption that SAT is one of these problems, why shouldn't the same rule apply. You've already made the assumption we can reduce its running time from exponential to polynomial, so why would it stop at some high polynomial?

If we are going to talk about the hypothetical flying pig P = NP world, let my algorithms run fast.
Computational Complexity published first on Computational Complexity