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) = cnk 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.
Well his point seems to be $P\neq NP$ implies complexity theory may not be practical. If the whole point is to show $P$ not $NP$ then well what is the point of the problem?
ReplyDeletewe can for all practical purposes solve NP-complete problems -
ReplyDeleteThat can't really be true considering that the common encryption algorithms are effective in practice.
Are theorists (specifically when wearing the computational complexity hat) ever driven by real world applications? Algorithm theorists perhaps aspire for their algorithms to be used some day.
ReplyDeleteI am not aware of any ideas and methods that hard core application oriented folks (especially with machine learning flavor) could bring to hard core theorists (and vice versa); perhaps I am being pessimistic.
Machine learning folks are having their field day in the sunshine and are truly relishing it (perhaps also rubbing it in into others in different fields).
I don't believe theorists ever had short term horizons for their science; their endeavors therefore cannot be quantified with a tangible easy-to-define (and verify) metric. The society has valued their work in the past and one hopes will continue to do so in the future despite the comings and goings of new technologies.
What if AI can self-educate itself to solve TCS problems better than any theorist, in the same way that AlphaZero self-trained itselt to beat all chess masters and other chess programs?
ReplyDelete... nearly all the known problems we know that sit in polynomial time have practical efficient solutions ...
ReplyDeleteThat is arguable: For example, consider the (rightly) celebrated log-space algorithm of Omer Reingold for st-connectivity in undirected graphs. It has a polynomial runtime, O(n^c), but c >> 10^9.
see https://cstheory.stackexchange.com/questions/1063/time-complexity-analysis-for-reingolds-ust-conn-algorithm
... If P = NP we can solve AI! ...
ReplyDeleteThat argument holds if you use AI for very "formal" applications. Even if you have an efficient NP algorithm for NP, to handle "natural" problems like speech recognition, language translation, OCR, ... you would end up doing things similar to what AI people do now.