You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

jkaufman comments on Efficient Open Source - Less Wrong Discussion

11 [deleted] 15 March 2015 09:24PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (39)

Comments (39)

You are viewing a single comment's thread. Show more comments above.

Comment author: jkaufman 17 March 2015 05:26:02PM 0 points [-]

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.
Comment author: eternal_neophyte 17 March 2015 09:11:48PM *  0 points [-]

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 :)

Powered by Reddit Powered by Reddit