Maybe I didn’t articulate my point very well. These problems contain a mix of NP-hard compute requirements and subjective judgements.
Packing is sometimes a matter of listing everything in a spreadsheet and then executing a simple algorithm on it, but sometimes the spreadsheet is difficult to fully specify.
Playing Pokemon well does not strike me as an NP-hard problem. It contains pathfinding, for which there are efficient solutions, and then mostly it is well solved with a greedy approach.
If I understand your position—you’re essentially specifying an upper bound for the types of problems future AI systems could possibly solve. No amount of intelligence will break through the NP-hard requirements of computing power.
I agree with that point, and it’s worth emphasising but I think you’re potentially overestimating how much of a practical limit this upper bound will affect generally intelligent systems. Practical AI capabilities will continue to improve substantially in ways that matter for real-world problems, even if the optimal solution for these problems is computationally intractable.
Packing is sometimes a matter of listing everything in a spreadsheet and then executing a simple algorithm on it, but sometimes the spreadsheet is difficult to fully specify.
I agree that problem specification is hard, but it’s not NP-hard—humans do it all the time. This is the type of problem I’d expect future AI systems to be really good at. You seem to be implying that to pack a bag for a holiday we need to write a big spreadsheet with the weight and utility of each item and solve the problem optimally but no-one does this. In practice, we start packing the bag and make a few executive decisions along the way about which items need to be left out. It’s slightly suboptimal but much more computationally efficient.
Playing Pokemon well does not strike me as an NP-hard problem. It contains pathfinding, for which there are efficient solutions, and then mostly it is well solved with a greedy approach.
I agree that Pokémon is probably not NP-hard, this is exactly the point. The reason Pokemon is hard is because it requires a lot of executive decisions to be made.
Humans don’t beat Pokémon by laying out all possible routes and applying a pathfinding algorithm, they start going through the game and make adjustments to their approach as new information comes in. This is the type of problem I’d expect future LLM’s to be really good at (much better than humans.)
Maybe I didn’t articulate my point very well. These problems contain a mix of NP-hard compute requirements and subjective judgements.
Packing is sometimes a matter of listing everything in a spreadsheet and then executing a simple algorithm on it, but sometimes the spreadsheet is difficult to fully specify.
Playing Pokemon well does not strike me as an NP-hard problem. It contains pathfinding, for which there are efficient solutions, and then mostly it is well solved with a greedy approach.
If I understand your position—you’re essentially specifying an upper bound for the types of problems future AI systems could possibly solve. No amount of intelligence will break through the NP-hard requirements of computing power.
I agree with that point, and it’s worth emphasising but I think you’re potentially overestimating how much of a practical limit this upper bound will affect generally intelligent systems. Practical AI capabilities will continue to improve substantially in ways that matter for real-world problems, even if the optimal solution for these problems is computationally intractable.
I agree that problem specification is hard, but it’s not NP-hard—humans do it all the time. This is the type of problem I’d expect future AI systems to be really good at. You seem to be implying that to pack a bag for a holiday we need to write a big spreadsheet with the weight and utility of each item and solve the problem optimally but no-one does this. In practice, we start packing the bag and make a few executive decisions along the way about which items need to be left out. It’s slightly suboptimal but much more computationally efficient.
I agree that Pokémon is probably not NP-hard, this is exactly the point. The reason Pokemon is hard is because it requires a lot of executive decisions to be made.
Humans don’t beat Pokémon by laying out all possible routes and applying a pathfinding algorithm, they start going through the game and make adjustments to their approach as new information comes in. This is the type of problem I’d expect future LLM’s to be really good at (much better than humans.)