Содержит ли P языки, существование которых не зависит от PA или ZFC? (Сообщество TCS вики)

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

Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества.

обзор

Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности $P$  - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два взаимодополняющих подкласса:

• гностические языки и ТМ (которые можно проверить / понять), по сравнению с
• загадочные языки и ТМ (которые невозможно проверить / понять).

Определения: гностические против загадочных чисел, ТМ и языков

В рамках аксиомы PA и ZFC мы различаем гностические и загадочные машины и языки Тьюринга следующим образом:

Д0   Мы говорим , что вычислимый вещественное число   является гностическим тогда и только тогда он связан с непустым множеством ДЧА, с каждой ТМ , указанной в ПА в качестве явного списка чисел , содержащих действительный код на универсальном ТМ, что для любой точности е Если в качестве входных данных указано > 0 , то каждая ТМ (в ZFC) может быть остановлена ​​с выходным числом o, которое, как можно предположить, (в ZFC) удовлетворяет условию r - ϵ < o < r + ϵ .$r$$\epsilon\gt0$$o$$r-\epsilon\lt o\lt r+\epsilon$

Замечание   Известно, что некоторые вычислимые вещественные числа не являются гностическими (конкретный пример см. В ответе Рафаэля Рейцига на вопрос Джкффа « Существуют ли неконструктивные доказательства существования алгоритма? »). Чтобы избежать соприкосновения с этими вычислимыми, но пока неуклюжими числами, наложено ограничение на то, что показатели времени выполнения могут быть вычислены с помощью ТМ, которые явно перечислены в PA (в отличие от ТМ, неявно указанных в ZFC). Для дальнейшего обсуждения см. Раздел « Определения» (ниже).

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

Чтобы заглянуть в будущее, заключительное определение ( D5 ) определяет идею канонически загадочного решения TM , определение которого разработано с целью избежать сокращений, которые (тривиально) маскируют загадочные вычисления путем наложения вычислительных лишних эпи-вычислений. Обоснование и источники этого ключевого определения обсуждаются позже - под заголовком « Определительные соображения»  - и с благодарностью отмечаются комментарии Тимоти Чоу, Питера Шора, Сашо Николова и Луки Тревизана.

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

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

Мы говорим, что машины Тьюринга, которые не являются загадочными, являются гностическими ТМ.

D2   Мы говорим, что машина Тьюринга для принятия решения является эффективной, если она имеет гностический показатель времени выполнения  , так что язык L, который принимает M, не принимается никакими другими TM, имеющими гностический показатель времени выполнения меньше  r .$r$$r$

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

Для того, чтобы выразить D3 другой способ, язык маскировочный тогда и только тогда ТМС , которые принимают этот язык наиболее эффективно сами по себе являются загадочным.

Мы говорим, что языки не загадочные, это гностические языки.

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

D5   Мы говорим, что сильно загадочный TM канонически загадочный, если он эффективен.

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

Задаваемые вопросы

Следующая гипотеза C0 является естественной и (по-видимому) открытой:

C0   Класс сложности P содержит хотя бы один загадочный язык.

Заданы три вопроса, Q1 - Q3 , из которых первый:

Q1   Является ли гипотеза C0 независимой от PA или ZFC?

В предположении, что C0 истинно - либо доказуемо в ZFC, либо в качестве независимой аксиомы, которая является дополнительной к ZFC, - естественными являются два следующих вопроса:

Q2   Может ли хотя бы один загадочный язык в P быть представлен конкретно, то есть представлен как словарь явных слов в конечном алфавите, который включает все слова вплоть до любой заданной длины? Если так, покажите такой словарь.

Q3   Может ли по крайней мере одно канонически загадочное решение TM быть представлено конкретно, то есть как вспомогательное описание для построения физической машины Тьюринга, которая решает (за полиномиальное время) все слова из словаря Q2 ? Если это так, создайте такую ​​машину Тьюринга и, используя вычисления, покажите загадочный словарь языка Q2 .

Определения соображений

Определение D0 подразумевает, что каждое гностическое действительное число вычислимо, но известно, что некоторые вычислимые действительные числа не являются гностическими. Примеры см ответы на MathOverflow от Michaël Cadilhac и Райан Уильямс и на ТКС StackExchange по Рафаэль Reitzig . В более общем смысле определения D0 – D5 созданы так, чтобы исключить ссылки на не гностические показатели времени выполнения.

Как обсуждалось в вики TCS « Содержит ли P непонятные языки? », Определения D0 – D5 гарантируют, что каждый загадочный язык принят хотя бы одной TM, которая является канонически загадочной. (Отметим также, что в данном вопросе слово «загадочный» заменяет менее описательное слово «непонятный», используемое в вики).

Более того - ввиду D3 (a) и D3 (b)  - не существует вычислительно тривиального редукции канонически загадочного ТМ к гностическому ТМ, который доказуемо распознает тот же язык. В частности, D3 (a) и D3 (b) препятствуют стратегиям уменьшения полилимитера, которые были изложены в комментариях Питера Шора и Сашо Николова , и независимо от Луки Тревизана , и также препятствует полиномиально синхронизированной стратегии сокращения Тимоти Чоу , все из которых аналогичным образом маскируют загадочные вычисления, накладывая излишне вычислительные эпи-вычисления .

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

Методологические соображения

В обзоре Ланса Фортнау « Состояние проблемы P против NP » рассматриваются методы установления независимости (или иного характера) гипотез в теории сложности; особенно желательны предложения относительно того, как методы, которые анализирует Лэнс, могут помочь (или нет) ответить на вопрос Q1 .

Понятно, что многие дальнейшие вопросы закономерны. Например, гипотеза Хартманиса-Стернса вдохновляет нас на вопрос: «Существуют ли загадочные мультитейп-машины Тьюринга в реальном времени? Является ли их существование (или нет) независимым от PA или ZFC?»

Соображения типа Цайльбергера

В случае, если на вопрос Q1 дан ответ «да», то оракулы, определяющие членство в существуют за пределами PA или ZFC, и, следовательно, существенный элемент современной теории сложности (в настоящее время) неизвестно, находится ли он в какой-либо формальной системе логика. $P$

В этом отношении теория сложности стоит в стороне от большинства математических дисциплин, так что опасения, которые Дорон Цейлбергер выражает в своем недавнем « Мнении 125: Теперь, когда Алану Тьюрингу исполнилось 100 лет, пришло время по-новому взглянуть на его основополагающие вклады». , который сделал много хорошего, но и много вреда ", возможно, являются обоснованными.

В качестве критерия Z0    (! Q1  ) && (! C0  ) озабоченность Цейлбергера принимает явную форму , что эквивалентно следующему критерию:$\equiv$

Z0:   критерий чувствительности Цейлбергера.   Определения класса сложности P   называются чувствительными к Цейлбергеру, если все языки в P доказуемо гностичны.

В настоящее время неизвестно, является ли определение Стивена Кука класса сложности P   чувствительным к Цейлбергу.

Мотивационные соображения

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

C1   Пусть и N P ′ - гностические ограничения P и N P соответственно. Тогда P ′ ≠ N P ′ либо доказуемо, либо опровергаемо в PA или ZFC.$P'$$NP'$$P$$NP$$P' \ne NP'$

C2   (как явно доказано в PA или ZFC)$P' \ne NP'$

Ясно, что C2   C1 , и наоборот, возможно, что доказательство (мета) теоремы C1 может служить руководством к доказательству (более сильной) теоремы C2 .$\to$ 

Общая мотивация - это ожидание / интуиция / надежда на то, что для некоторых хорошо отлаженных различий между гностическими и загадочными ТМ и языками, доказательство С1 и, возможно, даже С2 может пролить свет - и даже иметь сравнимые практические значения - по-видимому, гораздо сложнее и глубже доказательство того, что . $P\ne NP$

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

Номенклатурные соображения

Из Оксфордского словаря английского языка (OED) мы имеем:

• гностический (прил.)  Относящийся к знанию; когнитивный; интеллектуальный   «Они [числа] существуют в витальной, гностической и умозрительной форме, но не в оперативной манере».

• загадочный (прил.)  Не сразу понятно; таинственный, загадочный   «Вместо простых Правил, полезных для Человечества, они [философы] навязывают грубые и темные предложения».

По-видимому, ни в одном математическом обзоре ранее не использовалось слово «гностический» в каком бы то ни было смысле. Тем не менее, внимание обращается на недавнюю статью Маркуса Крахта « Гнозис » ( Journal of Philosophical Logic , MR2802332), в которой используется смысл OED.

Очевидно, что ни в одном математическом обзоре не использовалось слово «загадочный» - в его техническом смысле - в связи с теорией сложности. Тем не менее, внимание обращается на статью Чарльза Х. Беннетта « Логическая глубина и физическая сложность » (в «Универсальной машине Тьюринга: обзор полвека» , 1988), в которой содержится отрывок

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

Соображения естественности, открытости и сложности

Естественность этих вопросов иллюстрирует тезис монографии Юриса Хартманиса « Возможные вычисления и свойства комплексной сложности» (1978), который:

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

Открытость и сложность этих вопросов в целом согласуются с заключением рецензии Лэнса Фортнау « Состояние проблемы P против NP » (2009), которое:

«Никто из нас действительно не понимает проблему P против NP, мы только начали очищать слои вокруг этого все более сложного вопроса».

Руководство по вики

Особенно интересными являются коррективы по определению и стратегии доказательства, конкретно относящиеся к вопросам Q1 – Q3 и широко освещающие гипотезы типа Гартманиса C1 – C2 .

Я думаю, что есть фундаментальная трудность с вопросом, который вы задаете здесь (и что вы задали в своем родственном вопросе о непонятных языках).

Грубо говоря, кажется, вы ищете язык такой, что$L$

, но ZFC не знаетчто L ∈ P .$L\in P$$L\in P$

Чтобы понять трудности , связанные с вашим вопросом, я думаю , вы должны сначала оценить , что есть принципиальная разница между интенсиональными и экстенсиональными определениями языка . Экстенсионально, L определяется тем , что слова или не являются членами L . То есть два языка L и L ' экстенсивно равны тогда и только тогда, когда они содержат точно такие же слова, что и члены. В противоположность этому , интенсиональная определение L описывает некоторые условия для слова , чтобы быть в L . Машина Тьюринга, которая принимает $L$$L$$L$$L$$L'$$L$$L$$L$Или первого порядка формула , что имеет место тогда и только тогда , когда X ∈ L , можно рассматривать в качестве интенсионального определения L .$\phi(x)$$x\in L$$L$

Дело в том, что каждый который (экстенсивно) в P допускает описание, которое является чрезвычайно простым, потому что P является так называемым "синтаксическим" классом сложности. А именно, просто возьмите полиномиально синхронизированную машину Тьюринга, которая заканчивается ровно в течение требуемого времени. Любая «разумная» система для занятий математикой, таких как PA или ZFC, собирается быть в состоянии доказать , что L ∈ P , если вы используете это простое описание L .$L$$P$$P$$L\in P$$L$

Так что если вы хотите , чтобы запутать ZFC, вы будете иметь , чтобы придумать какой - то (интенсионального) описание , что «слишком сложно» для ZFC признать как эквивалент незамысловатым описания L . Это возможно, но в некотором смысле слишком легко быть интересным. Все, что вам нужно сделать, это взять что-то, что мы знаем, что ZFC не понимает (например, свою собственную последовательность), и каким-то образом смешать это с определением L. Например, вот описание набора целых чисел:$L$$L$$L$

является четным, и x не кодирует доказательство того, что ZFC несовместим.$x$$x$

Предполагая, что ZFC непротиворечив, приведенная выше формула определяет набор четных целых чисел, но ZFC этого не знает. С немного больше мастерить, мы можем легко получить описание множества четных чисел , которые ZFC не смогут доказать в .$P$

В результате, если вы надеетесь, что причина того, что трудно доказать, что состоит в том, что в P есть языки , которые «слишком сложны», чтобы мы могли их рассуждать, то я думаю, что вы ошибаетесь дерево. Расширительно, каждый язык в P находится в P по тривиальным причинам. Вы можете испачкать воду, играя с непрозрачными описаниями языков в P , но это общий прием, который не имеет ничего общего с P, в частности, поэтому я не думаю, что он дает много понимания.$P\ne NP$$P$$P$$P$$P$$P$

Q1: $\:$Нет
Q2:$\:$ Да, по крайней мере, два-1 с двоичным

Лемма: $\:$ Каждая ТМ с вычислимым показателем времени выполнения, который по крайней мере 1, является трансцендентным.

Доказательство.
Пусть A и B - рекурсивно неразделимые множества .$\:$$M_0$$\:$$M_1$$\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$M_0$$M_1$$r_m$$\:m\in A\:$ тогда утверждение D1 верно] и [если $\:m\in B\:$ тогда утверждение D1 ложно]. $\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$r_m$$\:$Поэтому машина Тьюринга трансцендентна.


Определение:
по крайней мере два-1-в-двоичном - это набор неотрицательных целых чисел, двоичное
представление которых имеет по крайней мере два 1-х.$\:$ (держу пари, ты бы никогда не догадался ^ _ ^)

Определение:
M - это машина Тьюринга, которая сканирует двоичное представление
своего ввода, принимает, если найдет хотя бы две единицы, и отклоняет в противном случае.

Очевидно, что M принимает решение, по крайней мере, два-1-в-двоичном и имеет показатель времени выполнения 1, и никакая другая машина Тьюринга с меньшим показателем времени выполнения также не решает, по крайней мере, два-1-единицу в двоичном виде.
Тривиально,$\: 1\leq 1 \:$$1$$\;\;$По лемме М эффективна и трансцендентна.
Это означает, что по крайней мере два-1 с в двоичном виде также трансцендентно.

Поэтому TPCCC - это теорема PA (и ZFC), и,
по крайней мере, два-1-в-двоичном является конкретным трансцендентным языком.

$x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$$n$$x_n$$x_n$$x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$

$x$$\bf{ZF}$

$x > 1$$M'_x$$n$$N$$s$$N$$s$$|s|^x/\log(|s|)$$x$$M_x$$M'_x$$M_x$$M_x$$\mathcal O(|s|^y)$$y\ge x$$M_x$

$x$$M_x$$\mathcal O(|s|^2)$$x = 2$$\bf{ZF}$$\bf ZF$$\bf ZF$$M_x$$\bf ZF + Con(\bf ZF)$

$\bf ZF + \not Con(\bf ZF)$$\bf P$$\bf ZF$$\mathcal O(|s|^z)$$z$$\bf ZF$

$M_x$