<p>I think this can be done for problems with some specified <a href="http://en.wikipedia.org/wiki/Turing_degree" rel="nofollow">degree of unsolvability</a>. To quote from Wikipedia: "Every Turing degree is countably infinite, that is, it contains exactly $\aleph_0$ sets."</p>

<p>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.</p>

<p><strong>Remark:</strong> 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.</p>

<p>See also: <a href="http://www.ams.org/notices/200610/whatis-davis.pdf" rel="nofollow">Martin Davis, What Is...Turing Reducibility?, Notices of the AMS, 53(10), pp. 1218--1219, 2006.</a></p>

CC BY-SA 2.5
2010-11-01T02:23:38.680Z
My guess is that your idea only works for polynomial-time Turing degrees (that is, where two languages are in the same degree iff they are poly-time Turing reducible to one another).
Joshua Grochow
CC BY-SA 2.5
2010-11-01T09:37:05.853Z
@Joshua: Thanks. I think you're right. So, the answer must be changed as follows: Any undecidable problem, which has the same polynomial-time Turing degree as HALTING PROBLEM, can be converted to an NP problem by putting some bound on its resources (as described by the OP).
Sadeq Dousti
CC BY-SA 2.5
2010-09-13T02:51:45.477Z
2010-09-13T02:51:45.477Z
Sadeq Dousti
<p>As Jukka pointed out, the answer is trivially no for all undecidable problems. </p>

<p>A more reasonable question would be: <strong>Can every problem that is complete for the class of recursively enumerable languages be made NP-complete in a straightforward way?</strong> 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.)</p>

<p>So if we ask the even more reasonable question: <strong>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?</strong>, here the answer is <strong>yes</strong>. 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. </p>

<p>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.)</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-13T03:21:31.747Z
2010-09-13T03:34:35.120Z
2010-09-13T03:34:35.120Z
Ryan Williams
<p>Examples of bounded $NP$-complete variants of undecidable sets:</p>

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

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

<p>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) }</p>

<blockquote>
  <p>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?</p>
</blockquote>

CC BY-SA 2.5
2010-09-12T22:43:50.313Z
There are uncountably many undecidable problems but only countably many NP-complete problems.
Jukka Suomela
<cc.complexity-theory><np-hardness>
NP-complete variants of undecidable problems?
Mohammad Al-Turkistany
# NP-complete variants of undecidable problems?

(Asked by: username_0 on 2010-09-12)

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?

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: There are uncountably many undecidable problems but only countably many NP-complete problems.  

---

## 2 answers

### Answer by username_4 on 2010-09-13. Score: 14 | Accepted answer

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 by username_2 on 2010-09-13. Score: 1

I think this can be done for problems with some specified [degree of unsolvability](http://en.wikipedia.org/wiki/Turing_degree). 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.](http://www.ams.org/notices/200610/whatis-davis.pdf)

> **Comments:**
> **username_3**: My guess is that your idea only works for polynomial-time Turing degrees (that is, where two languages are in the same degree iff they are poly-time Turing reducible to one another).  
> **username_2**: @Joshua: Thanks. I think you're right. So, the answer must be changed as follows: Any undecidable problem, which has the same polynomial-time Turing degree as HALTING PROBLEM, can be converted to an NP problem by putting some bound on its resources (as described by the OP).  

---

