[Dylan16807]

When people talk about "limited time and/or memory" for a runtime they're almost certainly talking about something constant, or a small polynomial of the input size.

But yes, it should reduce to NP territory. If you actually had a nondeterministic CPU, then for most use cases you could fully evaluate these machines in seconds.

[a1369209993]

> limited time [to] a small polynomial of the input size.

This is backwards; I meant that if you have any time bound whatsoever, the number of inputs you can inspect is limited to (a architecture-specific finite multiple of) the number of operations you can execute (because inspecting a input is such a operation).

[Dylan16807]

I wasn't talking about your argument that the calculation is finite. I was talking about how N is chosen in the first place.