Заданный вопрос состоит в том, является ли следующий вопрос разрешимым:
Проблема Учитывая целое число и обещанная машина Тьюринга в P, является ли время выполнения относительно длины ввода ?
Узкий ответ «да», «нет» или «открытый» является приемлемым (со ссылками, наброском доказательства или обзором существующих знаний), но более широкие ответы также очень приветствуются.
Ответ
Эмануэле Виола опубликовала доказательство неразрешимости вопроса (см. Ниже).
Фон
Для меня этот вопрос возник естественным образом при разборе ответа Луки Тевизана на вопрос: требуются ли время выполнения для P ресурсов EXP для верхней границы? … Известны ли конкретные примеры?
Этот вопрос относится также к вопросу MathOverflow: какие наиболее привлекательные неразрешимые проблемы Тьюринга в математике? в варианте, в котором слово «математика» заменено на «инжиниринг», признавая, что оценка времени выполнения является повсеместной инженерной проблемой, связанной, например, с теорией управления и схемотехникой.
Таким образом, широкая цель при задании этого вопроса состоит в том, чтобы получить лучшее понимание / интуицию относительно того, какие практические аспекты оценки времени выполнения в классе сложности P возможны (то есть требуют вычислительных ресурсов в P для оценки), по сравнению с неосуществимым (то есть требовать вычислительных ресурсов в EXP для оценки), по сравнению с формально неразрешимыми.
--- редактировать (пост-ответ) ---
Я добавил теорему Виолы в вики сообщества сообщества MathOverflow "Привлекательные неразрешимые проблемы Тьюринга". Это первый вклад вики, связанный с классом сложности P; это свидетельствует о новизне, естественности и широком охвате теоремы Виолы (и ИМХО о ее красоте).
--- редактировать (пост-ответ) ---
Монография Юриса Хартманиса « Возможные вычисления и свойства доказуемой сложности» (1978) охватывает большую часть того же материала, что и доказательство Эмануэле Виолы.
источник
Ответы:
Проблема неразрешима. В частности, вы можете уменьшить проблему остановки следующим образом. Учитывая экземпляр проблемы остановки, создайте новую машину M ′, которая работает следующим образом: на входах длины n она имитирует M на x для n шагов. Если M принимает, сделайте цикл для n 2 шагов и остановитесь; в противном случае петля для п 3 шагов и остановки.( М, Х ) M' N M Икс N M N2 n3
Если останавливается на x, он делает это с шагом t = O ( 1 ) , поэтому время выполнения M ′ будет O ( n 2 ) . Если M никогда не останавливается, то время выполнения M ′ составляет не менее n 3 .M x t=O(1) M′ O(n2) M M′ n3
Следовательно , вы можете решить , если принимает й , решив , если время выполнения М ' является O ( N 2 ) или O ( п 3 ) .M x M′ O(n2) O(n3)
источник
Это перефразирование ответа Эмануэле Виолы с целью быть более понятным.
Показано , что данная проблема неразрешима за счет снижения общей проблемы остановки H к нему.P H
Теперь мы наблюдаем следующие последствия:
а также
источник
источник
Эта проблема была также решена в моей статье « Интенциональное содержание теоремы Райса » POPL'2008, где я доказываю, что никакая «клика сложности» не разрешима. Клика сложности - это класс программ, закрытых по программам с похожим поведением и сложностью. Я также предоставляет необходимые условия для полуразрешимых свойств.
Программы, выполняемые в O (n ^ k), являются кликой сложности в вышеприведенном смысле, поэтому набор не разрешим.
Результат также был недавно расширен для субрекурсивных настроек (таких как P) Мэтью Хойрупом: Разрешаемые свойства субрекурсивных функций (ICALP 2016).
источник
Для выяснения полноты, в то время как P-время состояние обещания также -полные, существует разрешимый набор коды S таким образом, что все машины в S полиномиально время и вопрос является завершить на .Σ02 S S Σ 0 2 SO(n2) Σ02 S
Чтобы доказать это, выберите полное , ф φ (х)⇔ ∃ к ∀ мΣ02 φ φ(x)⇔∃k∀mψ(x,k,m) ψ
источник
вот недавно новый более систематический анализ / углы / результаты по этому вопросу и связанные с ним, вводящие понятие "алгоритмическая проверяемость" и аналог Rice-th-th для теории сложности. Ниже приведен один соответствующий раздел из реферата, и есть много других связанных теорем, связанных с доказуемостью P против NP и т. д.
Почему концепция вычислительной сложности трудна для проверяемой математики / Хромкович
источник
Решение от 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 *, которая работает следующим образом:
Теперь мы наблюдаем следующие последствия:
M останавливается на x после максимум k (постоянных) шагов => T (M *) = O (1) и
M никогда не останавливается на x => T (M *) = O (n ^ 2 * f (n))
Следовательно, даже решить, является ли время выполнения произвольного DTM просто большим, чем постоянным, так же сложно, как и проблема остановки. □
источник