A problem can be in P and still not be computationally feasible; O(n^10000) algorithms are still in P.
Almost always a very good approximate answer is good enough. The travelling salesman problem is in NP, but we have efficient enough approximations (not just in P, but small exponents) that the benefit of getting to perfect is low.
The major implication I care about concerns the feasibility of A.I., specifically because I believe “analogy finding” and knowledge reuse to rest on tractable sollutions to the subgraph isomorphism problem.
You could build an AI which restricts itself to solving small cases of the problem, finding “petty” analogies, and growing more complex ones ontop. Any (computationally efficient) algorithm which could find isomorphisms for larger problems directly in polynomial time would blow a “bottom up” analogy finder out of orbit.
Though ofcourse if anyone reading could point out a method for finding subgraph isomorphisms on large graphs that is “good enough” by some standard, I’ll be happy to learn of it :)
I’ll just leave this here: http://math.stackexchange.com/questions/1892/the-practical-implication-of-p-vs-np-problem
I mostly agree with passve_fist:
A problem can be in P and still not be computationally feasible; O(n^10000) algorithms are still in P.
Almost always a very good approximate answer is good enough. The travelling salesman problem is in NP, but we have efficient enough approximations (not just in P, but small exponents) that the benefit of getting to perfect is low.
The major implication I care about concerns the feasibility of A.I., specifically because I believe “analogy finding” and knowledge reuse to rest on tractable sollutions to the subgraph isomorphism problem.
You could build an AI which restricts itself to solving small cases of the problem, finding “petty” analogies, and growing more complex ones ontop. Any (computationally efficient) algorithm which could find isomorphisms for larger problems directly in polynomial time would blow a “bottom up” analogy finder out of orbit.
Though ofcourse if anyone reading could point out a method for finding subgraph isomorphisms on large graphs that is “good enough” by some standard, I’ll be happy to learn of it :)