P содержит непонятные языки? (Сообщество TCS вики)

Ответ: неизвестно

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

Определения этой вики послужили отправной точкой для более новой вики TCS: « Содержит ли P языки, существование которых не зависит от PA или ZFC? (Вики сообщества TCS) ».

Более поздняя вики предпочтительна, потому что ее определения и номенклатура значительно сложнее, чем в этой более старой вики.

В частности, эта непонятная понятная понятная для Вики номенклатура и ТМ вытесняется в более новой вики загадочной гностической . Помимо подробных определений, которые, тем не менее, важны, две вики посвящены аналогичному классу вопросов. $\Leftrightarrow$ $\Leftrightarrow$

Дальнейшие ответы приветствуются

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

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

Ценный ответ Филиппа Уайта мотивировал дифференцированное определение ТМ, которые непостижимы, сильно непостижимы и канонически непостижимы (согласно приведенному ниже списку «градуированные определения непостижимости»).

Нижеследующее изложение вопроса в предварительном порядке включает ценные идеи и предложения, представленные Цуёси Ито, Марцио Де Биаси, Хаком Беннеттом, Рики Демером, Питером Шором, а также ценную публикацию в блоге Люки Тревизана .

Формальное определение

Непонятные машины Тьюринга (в рамках ZFC) определяются следующим образом:

D1 Для машины Тьюринга M, которая доказуемо останавливается для всех входных строк, M называется непонятным, если следующее утверждение не является ни доказуемым, ни опровержимым хотя бы для одного положительного полуопределенного действительного числа : $r$

Заявление: время выполнения M равно относительно длины ввода ${O}(n^r)$ $n$

Наоборот, M называется понятным, если оно не является непонятным.

Двусмысленность разрешима

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

Дальнейшими ссылками в этом отношении являются примечания к курсу Джереми Авигада « Неполнота с помощью проблемы остановки », эссе блога Скотта Ааронсона « Теорема Россера с помощью машин Тьюринга » и пост блога Луки Тревизана. Два интересных вопроса .

О существовании непонятных машин Тьюринга

То, что существуют непонятные машины Тьюринга, конкретно следует из конструкции Эммануэле Виолы и, в целом, из теории теорий сложности Юриса Хартманиса. В частности, конструкция Виолы обеспечивает с помощью методов заметок курса Джереми Авигада (насколько я понимаю) следующую лемму:

$\to$

Уважая естественность в определении непонятности

Естественно задаться вопросом, верно ли обратное значение для Последствия Виолы.

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

В частности, естественно требовать, чтобы мы не « неэстетично маскировали старые элементы непостижимости, вводя новые элементы непостижимости ». Ключевая проблема, связанная с заданным вопросом, сводится к «Существует ли естественное определение непостижимости?» ... который (учитывая обсуждение здесь TCS) мы, возможно, должны рассматривать как нетривиальный мета-вопрос, который может иметь более одного естественного ответа.

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

Градуированные определения непонятности

$r$ $r$

D3 Мы говорим, что язык L непостижим, если он принят (а) по меньшей мере одной машиной Тьюринга M, которая является одновременно эффективной и непостижимой, и, более того, (б) не существует эффективной и понятной ТМ, которая доказуемо (в ZFC) принимает L.

D4 Мы говорим, что непонятная ТМ сильно непостижима, если язык, который она принимает, непонятен.

D5 Мы говорим, что сильно непостижимая ТМ канонически непостижима, если она эффективна.

Эти определения гарантируют, что каждый непонятный язык будет принят по крайней мере одной ТМ, которая является канонически непостижимой, и, более того, - ввиду D3 (a) и D3 (b) - не существует тривиального полилимиторного преобразования канонически непонятной ТМ к понятной ТМ. что доказуемо признает тот же язык.

Три вопроса

Q1 Содержит ли класс сложности P непонятные языки?

Q2 Может ли хотя бы один непонятный язык быть представлен конкретно? (если так, приведите конструктивный пример).

Q3 Может ли хотя бы одна канонически непонятная ТМ быть представлена конкретно? (если так, приведите конструктивный пример).

мотивация

Непонятные свойства класса сложности P затрудняют понимание широкого класса проблем, которые (для первоначального автора этого вопроса ) включают загадку с голубыми глазами Терри Тао, игру Дика Липтона и Кена Ригана « Выбор урны» и их гибридизацию в контекст «Парадокса Ньюкомба» через игру « Сбалансированное преимущество Ньюкомба» .

Как гласит монография Юриса Хартманиса « Возможные вычисления и свойства доказуемой сложности» (1978):

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

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

Большое спасибо всем, кто предоставил комментарии и ответы.

cc.complexity-theory complexity-classes turing-machines decidability Джон Сидлес
источник

Пожалуйста, дайте определение термину «(машина Тьюринга), который решительно присутствует в P.»

Цуёси Ито

В задаче, сформулированной в определении «непонятно в P», что именно является входом? Является ли машина Тьюринга входной или постоянной? Кроме того, как вещественное число указывается в виде строки?

Цуёси Ито

r

$r$

M

$M$

Как упреждающе объяснил Сашо, проблема, указанная в определении «непостижимо» в пересмотре 4, разрешима для каждого М. Я боюсь, что вы делаете элементарную ошибку здесь. Если у вас все еще есть проблемы с пониманием, этот пост Рафаэля и ссылка в нем могут быть полезны. Я проголосовал, чтобы закрыть это как не реальный вопрос.

Цуёси Ито

C n^{k}

$Cn^k$

C

$C$

k

$k$

Ответы:

(Я ухожу в отставку, поскольку больше не имею отношения к той части ответа, которая только что объяснила, почему нет неразрешимых примеров проблемы / нет алгоритмов разноименного времени с неисчислимой временной привязкой)

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

$M$ $M$
$M$ $M'$

Таким образом, кажется, что ответ на ваш вопрос «нет»: любой язык, разрешимый в polytime на некоторой машине, определяется доказуемо polytime машиной. Но, возможно, ваш вопрос должен быть:

$M$ $M'$ $M$

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

Сашо Николов
источник

------ В математике и информатике существуют два разных значения этого слова, неразрешимые . Первым из них является теоретико-доказательный смысл, используемый в отношении теорем Геделя, когда утверждение не является ни доказуемым, ни опровержимым в определенной дедуктивной системе. ... Из-за двух значений слова неразрешимый термин « независимый» иногда используется вместо неразрешимого в смысле «не доказуемо и не опровергнуто».

Джон Сайдлз

Спасибо, Сашо! Я также пришел к этому признанию, но постулат можно изменить с помощью различия в Википедии: «В математике и информатике есть два разных значения слова неразрешимые . Первое из них - это теоретико-доказательный смысл, используемый в отношении теорем Геделя, это утверждение не является ни доказуемым, ни опровержимым в определенной дедуктивной системе ... Из-за двух значений слова неразрешимый термин « независимый» иногда используется вместо неразрешимого в смысле «ни доказуемо, ни опровергаемо». Таким образом, я надеюсь уточнить вопрос позже сегодня.

Джон Сайдлз

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

Джон Сайдлес

пожалуйста, проверьте мой обновленный ответ

Сашо Николов

Спасибо, Сашо. Я тоже должен сделать перерыв до завтра, однако при первом чтении ваше последнее предложение кажется очень плодотворным, и я надеюсь ответить на него в ближайшее время. Еще раз спасибо.

Джон Сайдлз

Просто расширенный комментарий, пытающийся интерпретировать вопрос.

$M$ ~~обещано остановить~~ $M$ ~~положительное полуопределенное действительное число~~ $r$ ~~вопрос~~ $Q_{M,r}$

ОПЦИЯ 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

ВАРИАНТ 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

И если вы спросите: «Хорошо, но можем ли мы вычислить значение 1 или 0, чтобы построить алгоритм, который отвечает на вопрос варианта 2?», Тогда мы вернемся к этому:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Марцио де Биаси
источник

Марзо, спасибо за этот ответ и за ваш комментарий выше. Двусмысленный термин «разрешимый» уже был отброшен - он означал разные вещи для разных сообществ - в пользу теоретико-доказательственной идиомы «ни доказуемости, ни опровержимости». К очереди уточняющих поправок к завтрашнему отредактированному варианту вопроса (который, будем надеяться, станет окончательным и точным изложением вопроса), перед вашим вариантом 1 будет добавлена фраза «Для всех n ». И, наконец, благодарность и благодарность расширены. Вам и всем, за помощь в постановке вопроса строго и четко.

Джон Сайдлз

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Марзо, хорошо и спасибо. Кроме того, чтобы установить «Смысл Виолы», мы должны присоединить аргумент из Раздела 3 примечаний к курсу Джереми Авигада (как связано с вопросом) к конструкции Виолы ... исправленный вопрос прояснит этот момент. Излишне говорить, что процесс уточнения определений оказался в 10 раз сложнее, чем я ожидал ... что, пожалуй, является основным вопросом. Еще раз спасибо.

Джон Сайдлз

Ответ на ваш вопрос № 1 определенно «нет». Как я полагаю, кто-то указал на (очень длинный) раздел комментариев, вы можете легко добавить «полилиминг» к машине. То есть, даже если вы не знаете, что такое r, если вы угадаете какое-либо целое число больше r (это, безусловно, возможно), вы можете настроить служебную машину, которая имитирует вашу «непостижимую» машину Тьюринга, и заставить ее прекратить работу за полиномиальное время ... без изменения языка, который машина Тьюринга вообще принимает. Таким образом, вы можете преобразовать любую «непостижимую» полиномиальную машину времени Тьюринга в «понятную» полиномиальную машину времени Тьюринга, а это означает, что в языке P нет языка, который можно было бы определить исключительно «непостижимыми» машинами Тьюринга.

Надеюсь, это поможет. Если я не полностью неверно истолковал ваш вопрос и ваши намерения, мой ответ, безусловно, правильный; это совсем не открытый вопрос.

Филип Уайт
источник

Кстати, если вам нужен хороший пример кандидата для того, что вы называете «непостижимым» алгоритмом, см. Scholarpedia.org/article/Universal_search . Универсальный алгоритм поиска для решения SAT придерживается вашего определения непонятного, если P = NP формально независим.

Филип Уайт

Вы знаете что-нибудь о последнем вопросе из моего ответа? Я считаю, что это единственный вопрос, который до сих пор не очевидно тривиален .. для меня это

Сашо Николов

@Philip White, определение тщательно продумано, чтобы избежать конструкции, которую вы предоставляете. Поскольку предположим, что время выполнения M неразрешимо для некоторого показателя степени r , и мы предполагаем значение r ' > r , и мы устанавливаем r' -полилимитер в модифицированной машине M ', которая распознает тот же язык, что и M, тогда для M' выражение «время выполнения M 'равно O (n ^ r) относительно длины ввода n», все еще неразрешимо. Однако я согласен с тем, что нам нужно тщательно продумать, исключены ли ВСЕ игры в кошки-мышки с полилимитерами, указанными оракулом (как и предполагалось), - и поэтому я проголосовал за ваш ответ!

Джон Сайдлес

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

Джон Сидлес

Извините, я должен был прочитать ответ Сашо Николова более внимательно; Я только что увидел слово "да", упс. Я посмотрю на последний вопрос и посмотрим, смогу ли я сказать что-нибудь полезное.

Филип Уайт