NP-полные варианты неразрешимых проблем?

Примеры ограниченных полных вариантов неразрешимых множеств:$NP$

Ограниченная задача остановки = { | NTM-машина останавливает и принимает течение шагов}М х $(M, x, 1^t)$$M$$x$$t$

Ограниченная плитка = { | есть плитка квадрата области плитками из }т 2$(T, 1^t)$$t^2$$T$

Ограниченная почтовая проблема соответствия = { | существует соответствующий набор домино, который использует не более k домино из набора домино T (включая повторяющиеся домино)}$(T, 1^t)$$k$$T$

Всегда ли возможно получить -полный вариант каждой неразрешимой задачи, наложив некоторые ограничения на вычисления? Есть ли другие естественные примеры такого рода?$NP$

Как указал Юкка, ответ тривиально нет для всех неразрешимых проблем.

Более разумным вопросом будет: можно ли сделать каждую задачу, которая является полной для класса рекурсивно перечислимых языков, NP-полной, простым способом? Я не уверен, что это верно в целом, но в особых случаях, которые вы упоминаете в своем вопросе (Bounded-Halting и Tiling), эти проблемы для RE завершены даже при «особых» полиномиальных сокращениях времени. (Я оставляю «специальное» в основном неопределенным в этом ответе, но необходимые свойства можно определить из него.)

Так что, если мы зададим еще более разумный вопрос: можно ли сделать каждую задачу, которая является полной (с помощью специальных сокращений по многим временам) для класса рекурсивно перечислимых языков, простым образом сделать NP-полную? здесь ответ да . Возьмем любую RE-полную задачу , определенную относительно машины Тьюринга M A, которая принимает пару входов ( x , y ) , такую, что x ∈ $A$$M_A$$(x,y)$ . Мы предполагаемчто существует полиномиальное сокращение времени от остановочных задачи к А . Определите "Bounded-A", чтобы быть набором пар ( x , 1 t ), таким, что есть y длины не более t, такой, что M A ( x , y ) останавливается в течение t шагов.$x \in A \iff (\exists y)[M_A(x,y)~\text{halts}]$$A$$(x,1^t)$$y$$t$$M_A(x,y)$$t$

Ясно , что «Ограниченность-А» находится в . Это также N P -полный, потому что мы можем уменьшить N P -полную Ограниченную проблему остановки до B-A за полиномиальное время (обратите внимание, что здесь вам нужны специальные свойства для сокращения R за полиномиальное время, чтобы гарантировать, что он переносится на Bounded-Halting как хорошо: то есть, вы должны быть в состоянии эффективно вычислить верхнюю границу t ' того, как долго M A ( R ( M , x ) , y ) должен бежать, предполагая, что M ( x ) останавливается в пределах$NP$$NP$$NP$$R$$t'$$M_A(R(M,x),y)$$M(x)$ шагов.)$t$

Теперь, есть ли язык, который является RE-полным при (скажем) сокращениях в два раза по экспоненте, но не при сокращениях по экспоненте? Для такой проблемы маловероятно, что вы можете тривиально изменить ее, чтобы получить -комплектную версию. Я предполагаю, что такая проблема может быть искусственно построена.$NP$

Я думаю, что это может быть сделано для проблем с определенной степенью неразрешимости . Цитата из Википедии: «Каждый Тьюринг степень счетный, то есть, она содержит ровно множеств.»$\aleph_0$

Затем, я полагаю, для каждой проблемы в той же степени неразрешимости существует некоторый тип ограничения ресурса (времени), который дает NP-полный язык.

Примечание: Возможно, мне следовало бы быть более консервативным, когда говорил «для каждой проблемы в той же степени неразрешимости». Может быть так, что приведенное выше утверждение верно только для класса задач, имеющих такую ​​же степень, как, скажем, проблема HALTING.

См. Также: Мартин Дэвис, Что такое ... сводимость по Тьюрингу ?, Уведомления AMS, 53 (10), с. 1218-1219, 2006.