NP-complete variants of undecidable problems?

Question

Examples of bounded $NP$-complete variants of undecidable sets:

Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps}

Bounded Tiling={ $(T, 1^t)$| there is a tiling of a square of area $t^2$ by tiles from $T$}

Bounded Post Correspondence Problem={ $(T, 1^t)$| there is a matching set of dominoes that uses at most $k$ dominoes from a set of dominoes $T$ (including repeated dominoes) }

Is it always possible to get $NP$-complete variant of every Undecidable problem by imposing some bounds on the computation? Are there other natural examples of this kind?

Answer 1

As Jukka pointed out, the answer is trivially no for all undecidable problems.

A more reasonable question would be: Can every problem that is complete for the class of recursively enumerable languages be made NP-complete in a straightforward way? I am not sure this is true in general, but in the special cases you mention in your question (Bounded-Halting and Tiling) these problems are complete for RE even under "special" polynomial time reductions. (I leave "special" mostly undefined in this answer, but the properties needed can be worked out from it.)

So if we ask the even more reasonable question: Can every problem that is complete (under special polytime reductions) for the class of recursively enumerable languages be made NP-complete in a straightforward way?, here the answer is yes. Take any RE-complete problem $A$, defined with respect to a Turing machine $M_A$ that takes a pair of inputs $(x,y)$, such that $x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$. We are assuming that there is a polynomial time reduction from the Halting Problem to $A$. Define "Bounded-A" to be the set of pairs $(x,1^t)$ such that there is a $y$ of length at most $t$ such that $M_A(x,y)$ halts within $t$ steps.

Clearly "Bounded-A" is in $NP$. It's also $NP$-complete because we can reduce the $NP$-complete Bounded Halting Problem to Bounded-A in polynomial time (Note that here you need special properties on the polynomial time reduction $R$ to ensure that it carries over to Bounded-Halting as well: i.e., you need to be able to efficiently compute an upper bound $t'$ on how long $M_A(R(M,x),y)$ needs to run, assuming that $M(x)$ halts within $t$ steps.)

Now, is there a language which is RE-complete under (say) doubly-exponential-time reductions but not under exponential-time reductions? For such a problem, it is unlikely that you can trivially modify it to get an $NP$-complete version. I would guess that such a problem can be artificially constructed.

Answer 2

I think this can be done for problems with some specified degree of unsolvability. To quote from Wikipedia: "Every Turing degree is countably infinite, that is, it contains exactly $\aleph_0$ sets."

Then, I guess, for each problem within the same degree of unsolvability, there is some type of resource (time) bound, which gives an NP-complete language.

Remark: Maybe I should have been more conservative when saying "for each problem within the same degree of unsolvability." It might be the case that, the above statement is only true for the class of problems possessing the same degree as, say, HALTING problem.

See also: Martin Davis, What Is...Turing Reducibility?, Notices of the AMS, 53(10), pp. 1218--1219, 2006.