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.
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.