Confusion #2: Why couldn’t we make similar counting arguments for Turing machines?
I guess a central issue with separating NP from P with a counting argument is that (roughly speaking) there are equally many problems in NP and P. Each problem in NP has a polynomial-time verifier, so we can index the problems in NP by polytime algorithms, just like the problems in P.
in a bit more detail: We could try to use a counting argument to show that there is some problem with a (say) <n2 time verifier which does not have any (say) <n1000 time solver. To do this, we’d like to say that there are more n2 verifier problems than n1000 algorithms. While I don’t really know how we ought to count these (naively, there are ℵ0 of each), even if we had some decent notion of counting, there would almost certainly just be more <n1000 algorithms than <n2 verifiers (since the n2 verifiers are themselves <n1000 algorithms).
I guess a central issue with separating NP from P with a counting argument is that (roughly speaking) there are equally many problems in NP and P. Each problem in NP has a polynomial-time verifier, so we can index the problems in NP by polytime algorithms, just like the problems in P.
in a bit more detail: We could try to use a counting argument to show that there is some problem with a (say) <n2 time verifier which does not have any (say) <n1000 time solver. To do this, we’d like to say that there are more n2 verifier problems than n1000 algorithms. While I don’t really know how we ought to count these (naively, there are ℵ0 of each), even if we had some decent notion of counting, there would almost certainly just be more <n1000 algorithms than <n2 verifiers (since the n2 verifiers are themselves <n1000 algorithms).
Thank you Kaarel—this the kind of answer I was after.