Robin_Z comments on My Childhood Role Model - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (59)
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.