Famously
Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, there $J\leq 9$, and $M$ is no general algorithm for testing Diophantine equations for solvabilitya natural number. But if we further restrict the The decision problem is whether or not a given instance has a solution so in natural numbers such that $\sum_{j=1}^J x_j \leq M$. With no upper bound M, the solution vector has a bounded norm problem is undecidable (with a specified bound), if I have the answer can be determined by brute forceliterature correct). With the bound, what is the computational complexity? If the equation does have such a solution, then the solution itself serves as a polytime certificate, putting it in NP. What else can be said about the complexity of this problem?
More generally, I think one could consider any "mass problem" with a corresponding undecidable decision problem and restrict the solution space to a finite subset and then ask about the corresponding complexity class.
Not sure if this is trivial or if I'm missing obvious references. Any pointers, even relevant technical search terms, would be helpful.
