Разрешены ли границы времени выполнения в P? (ответ: нет)

64

Заданный вопрос состоит в том, является ли следующий вопрос разрешимым:

Проблема   Учитывая целое число k и обещанная машина Тьюринга M в P, является ли время выполнения M O(nk) относительно длины ввода n ?

Узкий ответ «да», «нет» или «открытый» является приемлемым (со ссылками, наброском доказательства или обзором существующих знаний), но более широкие ответы также очень приветствуются.

Ответ

Эмануэле Виола опубликовала доказательство неразрешимости вопроса (см. Ниже).

Фон

Для меня этот вопрос возник естественным образом при разборе ответа Луки Тевизана на вопрос: требуются ли время выполнения для P ресурсов EXP для верхней границы? … Известны ли конкретные примеры?

Этот вопрос относится также к вопросу MathOverflow: какие наиболее привлекательные неразрешимые проблемы Тьюринга в математике? в варианте, в котором слово «математика» заменено на «инжиниринг», признавая, что оценка времени выполнения является повсеместной инженерной проблемой, связанной, например, с теорией управления и схемотехникой.

Таким образом, широкая цель при задании этого вопроса состоит в том, чтобы получить лучшее понимание / интуицию относительно того, какие практические аспекты оценки времени выполнения в классе сложности P возможны (то есть требуют вычислительных ресурсов в P для оценки), по сравнению с неосуществимым (то есть требовать вычислительных ресурсов в EXP для оценки), по сравнению с формально неразрешимыми.

--- редактировать (пост-ответ) ---

Я добавил теорему Виолы в вики сообщества сообщества MathOverflow "Привлекательные неразрешимые проблемы Тьюринга". Это первый вклад вики, связанный с классом сложности P; это свидетельствует о новизне, естественности и широком охвате теоремы Виолы (и ИМХО о ее красоте).

--- редактировать (пост-ответ) ---

Монография Юриса Хартманиса « Возможные вычисления и свойства доказуемой сложности» (1978) охватывает большую часть того же материала, что и доказательство Эмануэле Виолы.

Джон Сидлес
источник
В ответ на вопросы, заданные в блоге Лэнса Фортнау и Билла Гезарха, под заголовком «75 лет компьютерных наук», начиная с «Я часто хотел, чтобы Тьюринг трезво спросил:« Какие проверяемые процессы могут быть выполнены при вычислении число? »... вместо того, чтобы Тьюринг задавал роковой, более сложный вопрос:« Каковы возможные процессы, которые могут быть выполнены при вычислении числа? », следующий вопрос будет (приблизительно):« Существуют ли машины Тьюринга, которые доказуемо доказуемы? в NP, чье членство в P неразрешимо? "Это чтобы показать, что я все еще думаю об этом! :)
Джон Сидлес
2
Несмотря на то, что доказательство Эмануэле Виолы яснее, на Mathoverflow был задан очень похожий вопрос: Mathoverflow.net/questions/28056/…
Алекс тен Бринк,
Некоторые ответы и идеи в этой теме оказались релевантными для эссе / набора вопросов, которые Дик Липтон разместил в своем блоге «Потерянное письмо Годеля» ; этот набор эссе / вопроса «Начало работы с P = NP». URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
Джон Сидлес
Хотя границы в P неразрешимы, это не мешает попытаться (ограничивая себя далее). Пример приведен в этом историческом ответе
Артем Казнатчеев
1
Этот вопрос вдохновил следующую статью: arxiv.org/abs/1307.3648
Дэвид Дж

Ответы:

83

Проблема неразрешима. В частности, вы можете уменьшить проблему остановки следующим образом. Учитывая экземпляр проблемы остановки, создайте новую машину M ′, которая работает следующим образом: на входах длины n она имитирует M на x для n шагов. Если M принимает, сделайте цикл для n 2 шагов и остановитесь; в противном случае петля для п 3 шагов и остановки.(M,x)MnMxnMn2n3

Если останавливается на x, он делает это с шагом t = O ( 1 ) , поэтому время выполнения M будет O ( n 2 ) . Если M никогда не останавливается, то время выполнения M составляет не менее n 3 .Mxt=O(1)MO(n2)MMn3

Следовательно , вы можете решить , если принимает й , решив , если время выполнения М ' является O ( N 2 ) или O ( п 3 ) .MxMO(n2)O(n3)

Manu
источник
4
почему M должен остановиться на x (если он делает) за O (1) шагов?
Суреш Венкат
10
и x фиксированы независимо от n . Mxn
Ману
2
Очень умное доказательство, это вариация какого-то общеизвестного результата или вы только что придумали его?
Антонио Э. Поррека
3
@ Рафаэль: Это проблемная область, которую я не думаю, что мы решили. Некоторые сайты обмена стеками поощряют редактирование ответов других. У нас нет политики против этого, но, на практике, я почти никогда не видел, чтобы это было сделано. Один технический момент: если ответ отредактирован слишком сильно, он становится вики-сообществом, и @Emanuele не получит никаких дополнительных точек повторения, если после этого за его ответ будет проголосовано. Я действительно думаю, что дополнительное объяснение помогло бы уточнить: @Джон Сайдлз первоначально думал, что обещание не использовалось, но доказательство использует более сильное обещание: работает в n 2 или n 3 , а не только в P.Mn2n3
Аарон Стерлинг
2
@John: Пока не публикуется ссылка, рассмотрите это руководство .
Рафаэль
29

Это перефразирование ответа Эмануэле Виолы с целью быть более понятным.

Показано , что данная проблема неразрешима за счет снижения общей проблемы остановки H к нему.PH

(M,x)M(x)MxM

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Теперь мы наблюдаем следующие последствия:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

а также

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

H(M,x)P(M,2)PH

Рафаэль
источник
12

nCn+DC,DN

Cn+D

Андрей Бауэр
источник
1
Нет недостатка в необычном поведении маленьких одноразовых ТМ. :)
Каве
4

Эта проблема была также решена в моей статье « Интенциональное содержание теоремы Райса » POPL'2008, где я доказываю, что никакая «клика сложности» не разрешима. Клика сложности - это класс программ, закрытых по программам с похожим поведением и сложностью. Я также предоставляет необходимые условия для полуразрешимых свойств.

Программы, выполняемые в O (n ^ k), являются кликой сложности в вышеприведенном смысле, поэтому набор не разрешим.

Результат также был недавно расширен для субрекурсивных настроек (таких как P) Мэтью Хойрупом: Разрешаемые свойства субрекурсивных функций (ICALP 2016).

Андреа Асперти
источник
2

Σ20

Для выяснения полноты, в то время как P-время состояние обещания также -полные, существует разрешимый набор коды S таким образом, что все машины в S полиномиально время и вопрос является завершить на .Σ20SSΣ 0 2 SO(n2)Σ20S

Чтобы доказать это, выберите полное , ф φ (х) к мΣ20φφ(x)kmψ(x,k,m)ψ

φ(x)O(n2)n

kn
m<nψ(x,k,m)

n2

cn2+cΠ10Σ20

Дмитрий Тарановский
источник
-1

вот недавно новый более систематический анализ / углы / результаты по этому вопросу и связанные с ним, вводящие понятие "алгоритмическая проверяемость" и аналог Rice-th-th для теории сложности. Ниже приведен один соответствующий раздел из реферата, и есть много других связанных теорем, связанных с доказуемостью P против NP и т. д.

  • Почему концепция вычислительной сложности трудна для проверяемой математики / Хромкович

    Во-первых, мы доказываем теорему Райса о недоказуемости, утверждая, что каждая нетривиальная семантическая проблема о программах почти не везде разрешима в алгоритмически проверяемой "AV"-математике. Используя это, мы показываем, что существует бесконечно много алгоритмов (программ, которые являются доказуемо алгоритмами), для которых не существует доказательств того, что они работают за полиномиальное время или что они не работают за полиномиальное время. ...

    Обратите внимание, что если P! = NP доказуемо в AV-математике, то для каждого алгоритма A доказано, что «A не решает СООТВЕТСТВИЕ или A не работает за полиномиальное время». Интересно, что мы, наконец, показываем, что существуют алгоритмы, для которых невозможно доказать, что они не работают за полиномиальное время, и что они не решают СООТВЕТСТВИЕ. Более того, существует алгоритм, решающий УСТОЙЧИВОСТЬ, для которого в AV-математике невозможно доказать, что он не работает за полиномиальное время.

    Кроме того, мы показываем, что P = NP подразумевает существование алгоритмов X, для которых утверждение «X решает УСТОЙЧИВОСТЬ за полиномиальное время» не доказуемо в AV-математике.

ВЗН
источник
-3

Решение от Viola можно обобщить на любое время работы (кроме поли): проблему остановки можно уменьшить следующим образом. Учитывая экземпляр (M, x) проблемы остановки, создайте новую машину M ′, которая работает следующим образом: на входах длины n она имитирует M на x для шагов f (n) или пока M не остановится, где f (n) ) - любая произвольная возрастающая функция (больше, чем константа) от n. .

Если M останавливается на x, он делает это с шагом T = O (1), поэтому время выполнения M ′ будет O (1). Если M никогда не останавливается, то время выполнения M ′ равно O (n ^ 2 * f (n)).

Следовательно, вы можете решить, принимает ли M x, решив, является ли время выполнения M 'O (1) или O (n ^ 2 * f (n)).

Затем вспомогательный код от Рафаэля может быть обобщен соответственно:

Пусть (M, x) - любой случай проблемы остановки, то есть мы должны решить, останавливается ли M на x. Построить детерминированную машину Тьюринга (DTM) M *, которая работает следующим образом:

  1. M * (вход) = {
  2. n: = 0
  3. Прочитать первый символ из ввода
  4. Loop:
  5. n: = n + 1
  6. Имитируйте M (x) для f (n) шагов или пока M (x) не остановится
  7. Прочитать следующий символ из ввода
  8. Цикл до окончания end_of_input или пока M (x) не остановится
  9. }

Теперь мы наблюдаем следующие последствия:

M останавливается на x после максимум k (постоянных) шагов => T (M *) = O (1) и

M никогда не останавливается на x => T (M *) = O (n ^ 2 * f (n))

Следовательно, даже решить, является ли время выполнения произвольного DTM просто большим, чем постоянным, так же сложно, как и проблема остановки. □

Андре Луис Барбоса
источник
2
MO(n)M
Для достаточно большого n, если M (x) останавливается, то его моделирование также останавливается и возвращается к M * в течение n0 (постоянных) шагов.
Андре Луис Барбоза,