Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
There are uncountably many undecidable problems but only countably many NP-complete problems. –  Jukka Suomela Sep 12 '10 at 22:43
add comment

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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 Nov 1 '10 at 2:23
    
@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 Nov 1 '10 at 9:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.