Saturday, February 4, 2012

P ≠ NP?

In theoretical computer science a distinction is made between branch-and-bound problems, and stuff that is computed in linear time. Solutions for NP problems try all possibilities, but for every found potential solution, its correctness can be checked in linear time. Shortest route from Boston to New York? Try'em all! If you have the final solution will be blatantly obvious; is New York in the list? If yes, you are done. P problems are anything efficiently solveable. Almost all of the applied mathematics is in P.

I argue that fussing over P ≠ NP is pointless and waste of energy. Feynman once said [paraphrasing] "some problems are just harder to compute [numerically]". So he was like "so what?". NP problems are foreign to physicist because their math is designed to keep them in P. If they come across intractable computation, they will throw simulation, other numerical tricks at the problem, but this either a) never happens, or b) won't be pursued until it is absolutely necessary. Algebraic derivation continues for a long time, twists and turns, sometimes in order to avoid intractability, sometimes for other reasons; and when finally there is a formula, usually it is already in P.

Some argue that the data generated by the Internet, images, video, sound, result in problems that are inherently in NP. I disagree. PDE based methods are applied to image processing successfully, and noone knows how much in P we can remain and still succeed solving these problems, because we haven't tried them yet. To me, pattern equals tractable math and that equals P.

Surely being able to solve NP problems, using paralellism, quantum computers, multicore architecture is necessary, a different research track on its own, what I am saying is there is a wealth of mathematics, modeling that is essentially P material. Mathematics, applied or not, is mostly about exploiting properties of numbers so they give us computable solutions in linear time. I am using the word exploitation here, with good reason. Some tricks are akin to dressing up a monkey and making it dance. Monkey dont know it, but it is dancin, and doing something for its viewers, conciously or not. That takes genius, creativity, understanding the problem domain and a good amount of mad skillz.