[fnrslvr]

> call the time bound N

Call the time bound c|x|^k, where x is the input and c and k are constants.

I see what point you're making, and I agree that you get yourself a nice, merely coNP-complete problem if you're willing to cut off the space of inputs at a point by enforcing a constant time bound or whatever. More than anything, this kind of argument makes me shudder at just how hard the very worst stuff in NP must be.

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

[a1369209993]

> to cut off the space of inputs at a point by enforcing a constant time bound

That is literally the problem statement you gave. I was pointing out that it is very much not undecidable.

It might be (almost certainly is, in this case) computationally intractable both in the general case and in practice, but it's still decidable.