Являются ли неразрешимые атрибуты P препятствием для выбора P против NP? (ответ: возможно)

Заданы пять связанных вопросов, и ожидается единый интегрированный ответ:

• В1: Существуют ли языки , которые распознаются только теми машинами Тьюринга в  , показатели времени выполнения которых неразрешимы ?$L$$P$
• Вопрос 2: Можно ли конечно построить примеры этих машин Тьюринга?
• Вопрос 3: Можно ли конкретизировать эти машины Тьюринга? ( например , с помощью оракулов, которые «угадывают» их, а не создают их окончательно).
• Q4: Какие другие атрибуты P (кроме показателей времени выполнения) в настоящее время известны как неразрешимые? Для каких атрибутов этот вопрос открыт?$P$
• Q5: Неразрешимые атрибуты препятствуют разрешимости ?P ≠ N P$P$$P \ne NP$

Обратите внимание на слово «исключительно» в Q1 (исключая предложенный ответ Ланса Фортнау).

Выводы и переход в вики сообщества

• Заданный вопрос: «Являются ли неразрешимые атрибуты P препятствием для выбора P по сравнению с NP?», Является открытым и считается сложным, как и многочисленные конкретные вопросы (такие как Q1–4 выше), которые естественно связаны с ним.

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

• Этот класс вопросов недостаточно изучен, поэтому задача поиска строгих доказательств тесно связана с проблемой выбора хороших начальных определений.

• Вдумчивые замечания и проницательные наброски, предоставленные Travis Service и Alex ten Brink, получили признание и оценку.

Поскольку вопрос является открытым, и поскольку он обсуждается в нескольких математических цепочках блогов ( 1 , 2 , 3 , 4 , 5 , 6 ), этот вопрос был помечен для преобразования в вики сообщества.

Обновление II и резюме

Мне стало известно, что монография Юриса Харманиса « Возможные вычисления и свойства комплексной сложности » 1978 года может быть прочитана как подробный ответ на вопросы 1–5 . Кроме того, (превосходные) эскизы для доказательства Q1 и Q4, представленные ниже Travis Service и Алексом тен Бринком, обеспечивают современное подтверждение и расширение общих выводов Хартманиса о том, что:

Результаты о сложности вычислений весьма радикально изменятся, если мы рассмотрим только те свойства вычислений, которые могут быть формально доказаны (выделено Хартманисом) ...

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

Мы [должны] рассмотреть возможность того, что эта знаменитая проблема [ $P\overset{?}{=}NP$ ] не может быть разрешимо в формализованной математической теории, такой как теория множеств.

Как из монографии Хартманиса, так и из ответов, предоставленных Трэвисом и Алексом, очевидно , что вопросы 1–5 значительно превосходят современное состояние теории сложности. Более того, эти вопросы / ответы, очевидно, являются достаточно тонкими, так как требуют тщательной корректировки определений и обоснования изложения в монографии… что, я надеюсь, не отговорит людей от публикации дальнейших ответов. :)

Для дальнейшего технического обсуждения см. Ответ Джоэла Дэвида Хэмкинса на MathOverflow на вопрос: может ли проблема быть одновременно полиномиальным временем и неразрешимой? (рекомендуется Алекс тен Бринк).

Если в монографии Хартманиса вместо «вычисления функций» заменить фразу «симуляция динамики», результат может быть прочитан как трактат о теоретико-сложных границах системотехники… это практическая причина, почему мы, инженеры, заботимся об этих проблемы.

Противоположное мнение Хартманису было недавно высказано Одедом Голдрайхом в письме редактору CACM под названием «О вычислительной сложности» :

К сожалению, в настоящее время у нас нет хороших теоретических ответов на большинство естественных вопросов, касающихся эффективных вычислений. Это происходит не потому, что мы задаем неправильные вопросы, а потому, что эти вопросы очень сложные.

(Конечно) вполне возможно, что мнения Хартманиса и Гольдрайха окажутся правильными, например, формальное доказательство неразрешимости отделимости PvsNP может быть разумно рассмотрено как обоснование обеих точек зрения.

Обновить я

Вдумчивые комментарии (ниже), сделанные Travis Service и Алексом Тен Бринком, предполагают (по сути), что в первом квартале фраза «неразрешимый» не является синонимом «не поддается достоверному определению», и что ответы на вопрос 2–5 могут зависеть от этого различия. Для меня не совсем ясно, какой выбор определений приведет к самым сильным теоремам, а также лучше всего отражает нашу интуицию класса P. Ответы и комментарии, касающиеся этого вопроса, приветствуются.

Вспоминается замечание Феликса Кляйна в « Элементарной математике с передовой точки зрения: геометрия» (1939):

Другим примером концепции, которая встречается с большей или меньшей точностью в наивном восприятии пространства, которое мы должны добавить в качестве дополнения к нашей системе геометрии, является понятие (произвольной) кривой . Каждый человек считает, что он знает, что такое кривая, пока он не выучил так много математики, что бесчисленные возможные отклонения сбивают их с толку.

Как с кривыми, так и с языками, принятыми машинами Тьюринга в  ... то, что когда-то казалось (для меня) самым простым и естественным из всех классов сложности, теперь смущает меня (бесчисленное множество?) Непроверяемых и / или неразрешимых атрибутов его членов , Широкая мотивация в вопросе 1–5 заключалась в том, чтобы найти путь через эту путаницу, но ответы, данные до сих пор (Travis Service и Alex ten Brink), дали дополнительные основания для путаницы!$P$

Поколение математиков Кляйна изо всех сил пыталось найти хорошие определения для кривых и других фундаментальных элементов теории множеств, геометрии и анализа. Обзор элементарного уровня можно найти в обсуждении Википедии о Александер Рогатой Сфере

      
      Вложение сферы в R3

В течение 20-го века анализ "диких многообразий", таких как сфера Александра, помог прояснить различия между топологическими многообразиями, кусочно-непрерывными многообразиями и дифференциальными многообразиями. Точно так же в 21-м веке, возможно, уточнения определений, связанных с , помогут приручить дикие языки P и дикие машины Тьюринга ... хотя определить подходящие уточнения будет нелегкой задачей.$P$$P$

Фон

Эти взаимосвязанные вопросы возникают из вики-вопросов сообщества MathOverflow « Каковы наиболее привлекательные неразрешимые проблемы Тьюринга в математике? » И « Какие понятия используются, но не четко определены в современной математике? » В частности, Колин Тан попросил , чтобы вопрос, заданный выше, был размещен как отдельный вопрос.

Для получения технической информации см. Вопрос TCS StackExchange « Разрешены ли границы времени выполнения в P? », В частности краткое доказательство Эмануэле Виолы, что ответ «нет». Отметим также, что аналогичные результаты доказаны Юрисом Хартманисом в его монографии « Возможные вычисления и доказуемые свойства сложности» (1978).

На этой неделе Ланс Фортноу / Bill GASARCH веблоге вычислительной сложности проводит их десятилетнюю опрос « Имеет ли или нет?$P=NP$ » - пятый и последний вопрос , который задают ПРИГЛАШАЕТ комментарий на Fortnow / GASARCH вопрос.

На вопрос 1 ответ - нет. Пусть - язык в P, и пусть M - любая машина Тьюринга за полиномиальное время, распознающая L (время выполнения которого считается неразрешимым). Для каждого k ∈ N пусть M k будет машиной Тьюринга, которая на входе x длины n сначала зацикливается на n k шагов, затем запускает M на x для n k + k шагов и принимает, если M принимает x (в пределах этих n k + $L$$P$$M$$L$$k \in \mathbb{N}$$M_k$$x$$n$$n^k$$M$$x$$n^k + k$$M$$x$$n^k + k$шаги) и отклоняет иначе. Время выполнения составляет Θ ( n k ) для каждого k .$M_k$$\Theta(n^k)$$k$

Так как работает в полиномиальное время существуют некоторые к ' ∈ N такой , что M работает в O ( п к ' ) (даже если мы не знаем , что к ' есть) и , следовательно , для всех к достаточно большого M к распознает L и имеет решаемое время выполнения.$M$$k' \in \mathbb{N}$$M$$O(n^{k'})$$k'$$k$$M_k$$L$

РЕДАКТИРОВАТЬ

Я думаю, что следующий ответ больше соответствует духу первоначального плаката с вопросом 1.

Теорема: существует язык такой, что если N - любая машина Тьюринга, которая решает L, то верно хотя бы одно из следующего:$L \in P$$N$$L$

1) Не существует доказательства того, что принимает L , или$N$$L$

2) Не существует доказательства того, что останавливается за f ( n ) шагов (для любой функции f ( n ) ).$N$$f(n)$$f(n)$

Эскиз доказательства. Пусть - машина Тьюринга, которая не останавливается на чистой ленте и для которой не существует доказательства того, что M не останавливается на чистой ленте (Результаты Hartmanis в области компьютерных наук показали, что M может быть эффективно найден).$M$$M$$M$

Пусть .$L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$

Поскольку не останавливается, L на самом деле является пустым языком, но доказательств этому нет (поскольку это доказало бы, что M не останавливается).$M$$L$$M$

Пусть будет любой машиной Тьюринга. Если существует и доказательство того, что N решает L, и доказательство того, что N выполняется за f ( n ) шагов, тогда выполнение N при выполнении на входе 1 предоставляет либо доказательство того, что M останавливается (т. Е. Если N принимает), либо что M делает не остановить (то есть, если N отклоняет). Таким образом, если N доказуемо решает L, тогда время выполнения N не разрешимо, и наоборот.$N$$N$$L$$N$$f(n)$$N$$1$$M$$N$$M$$N$$N$$L$$N$

Да, вы можете построить машину, для которой требуется время DTIME ( ) -DTIME ( n i ), где i - количество шагов, предпринятых конкретной машиной Тьюринга для остановки на пустой ленте. Простота построения и аналогичные конструкции применимы практически к любому нетривиальному аспекту P. Немного говорит нам о том, является ли P v NP неразрешимым: нет проблем с доказательством P ≠ EXP, несмотря на те же проблемы.$n^{i+1}$$n^i$$i$$\neq$

Подумав больше на эту тему, я думаю, что нашел (возможный) ответ для вашего Q4 .

• Q4: Какие другие атрибуты (кроме показателей времени выполнения) в настоящее время известны как неразрешимые? Для каких атрибутов P этот вопрос открыт?$P$$P$

Я доказал вариант теоремы Райс, который отвечает на ваш вопрос для большинства свойств. На этот раз я попытаюсь объяснить себя более четко (ответ Travis Service был гораздо более четким и более общим, чем мой предыдущий ответ).

Теорема: для любого свойства, имеющего некоторый непустой набор разрешимых бесконечных языков (но не конечных языков), неразрешимо, решает ли данная машина Тьюринга язык с этим свойством, когда обещано, что E всегда останавливается в O ( f ( n ) ) время, где f ( n ) = Ω ( n log n ) и f ( n ) = Ω ( g ( n ) ) , где g ( $E$$E$$O(f(n))$$f(n)=\Omega(n \log n)$$f(n)=\Omega(g(n))$ - время работы некоторой машины Тьюринга, определяющее язык с этим свойством.$g(n)$

Напомним, что машина Тьюринга (ТМ) с сегодняшнего дня выбирает язык, если он принимает все строки на языке и отклоняет все строки за пределами языка. Обратите внимание , что мы можем взять , чтобы быть чем - то иным , чем полином, поэтому теорема является более общей , чем просто P .$f(n)$$P$

Мы формализуем понятие «свойство» как некоторый свободно выбираемый набор языков «с этим свойством». Решение имеет ли язык свойства затем эквивалентно решение языка , является ли членом S . Так же , как и в теореме Райса, мы исследуем , если мы можем решить , имеет ли язык решается входной ТМ указанного свойства, и поэтому в S . Обратите внимание, что нам требуется S ⊆ R , т. Е. Чтобы S содержало только разрешимые языки.$S$$S$$S$$S \subseteq R$$S$

Обратите внимание, что речь идет о свойствах языков , а не ТМ. Ваш вопрос об показателях времени выполнения не является частным случаем этой теоремы. Свойства, скажем, , которые можно изучить с помощью S ⊆ P , могут вас заинтересовать больше, чем свойства TM, работающих за полиномиальное время. Вы можете совершать всевозможные жестокие поступки с ТМ, сохраняя при этом его правильность и время работы, но вы не можете делать то же самое с языками.$P$$S \subseteq P$

Требование, чтобы все языки в были бесконечными, является технической необходимостью для доказательства, но, поскольку все конечные языки разрешимы в постоянное время и поэтому обычно неинтересны, я не думаю, что это основной. Я ожидаю, что обобщенная версия, которая также позволяет конечным языкам быть верными.$S$

Доказательство теоремы . Предположим, нам дан некоторый TM с TM E в качестве параметра, такой, что P всегда останавливается и принимает, если E решает какой-то язык в S , и где E обещано всегда останавливаться со временем выполнения, как описано выше. Пусть ( A , i ) будет экземпляром для проблемы остановки, т. Е. A является TM, а i является входом для A , и теперь мы хотим решить, останавливается ли A на i .$P(E)$$E$$P$$E$$S$$E$$(A, i)$$A$$i$$A$$A$$i$

Так как мы предположили , был пуст, мы имеем некоторые s ∈ S . Поскольку S содержит только разрешимые языки, существует несколько TM C, решающих s . В частности, мы выбираем C со временем выполнения g ( n ), как предполагается в теореме. Теперь рассмотрим следующую ТМ:$S$$s \in S$$S$$C$$s$$C$$g(n)$

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

Легко видеть, что время работы этой ТМ соответствует требованиям теоремы, поскольку ТМ можно моделировать за время .$O(n \log n)$

$P(H)$$A$$i$$A$$i$$t$$H$$X$$|X| \geq t$$H$$S$$P(H)$

$A$$i$$C$$s \in S$$P(H)$$P(H)$

Я могу ответить на ваш Q1 отрицательно, тем самым ответив на Q2 и Q3 отрицательно. Я не уверен насчет Q4 или Q5 .

• $L$$P$

$M$$T$$M$$T$

$T$$k$$T$$O(n^k)$$M$$k$$T$$T$$k$ $T$

$L$$P$$T$$O(n^k)$$k$$L$$M$$k$$T$

$L$$P$$T$$L$$T$

$L$$P$$M$$T$$L$$T$$L$

$L$$P$$L$$O(n^k)$$M$$n$$n^{k+1}$$n^{k+2}$$L$

$M$$P$$L$$L$$k$$M$

Такое мышление о неразрешимости довольно распространено, по-видимому, я помню (блог?) Сообщение об очень похожей проблеме: вопрос был: «Можно ли решить, есть ли у Пи« последний ноль »», так ли Пи перестает иметь нули в своем десятичное представление, если вы идете вниз достаточно далеко, что представление. В настоящее время мы не знаем, так ли это. Возможно, мы даже не сможем доказать это, или это может быть даже независимо от наших систем аксиом (и, следовательно, недоказуемым). Но, поскольку ответ либо истинный, либо ложный, TM, возвращающий true, и TM, возвращающий false, решают проблему в любом случае, и, следовательно, проблема разрешима.

Я посмотрю, смогу ли я найти этот пост где-нибудь в Интернете.

Редактировать:

Я нашел это на Mathoverflow .