His argument still stands. The fact that combinatorial optimization is difficult doesn't change the fact that the problem space is finite and can theoretically be enumerated by a very fast computer with lots of space. This also means that the heuristics that are typically used (that dramatically reduce the problem space at a rate tied to the size of the problem) can make the exploration of potential solutions much easier than it once was.