Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Robin_Z comments on My Childhood Role Model - Less Wrong

29 Post author: Eliezer_Yudkowsky 23 May 2008 08:51AM

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

Comments (59)

Sort By: Old

You are viewing a single comment's thread.

Comment author: Robin_Z 24 May 2008 01:01:33PM 0 points [-]

Richard Kennaway: I don't know what you mean - the subset-sum problem is NP-hard (and NP-complete) and the best known algorithms can - given infinite resources - be run on lists of any size with speed O(2^(N/2) * N). It scales - it can be run on bigger sets - even if it is impractical to. Likewise, the traveling salesman problem can be solved in O(N^2 * 2^N). What I'm asking is if there are any problems where we can't change N. I can't conceive of any.