Сведение пороговых вопросов к вопросам конечности

12

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

В теории формальных языков, например, вместо использования чтобы охарактеризовать апериодический моноид, проще использовать проконечные слова, чтобы . $\exists n. x^{n+1} = x^n$ $x^{\omega+1} = x^{\omega}$

В теории сложности единственная известная мне техника, которая связана с этим, - это уловка заполнения, например, связывающая проблему P против NP с EXPTIME против NEXPTIME. Но естественный бесконечный эквивалент сложности вопросов будет вычислимым ».

Существуют ли результаты, связывающие сложность с вопросами вычислимости с использованием некоторого кодирования, так что порог ресурса теории сложности становится вопросом конечности вычислений в теории вычислимости?

cc.complexity-theory computability Людовик Патей
источник

2

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

T (n)

$T(n)$

M

$M$

n

$n$

M

$M$

\underset{n \to \infty}{lim sup} \log T (n) / n

$\limsup_{n \to \infty} \log T(n) / n$

Джошуа Грохов

5

Sipser доказал, что бесконечная четность не может быть вычислена (бесконечной) схемой любой постоянной глубины, которую вы можете рассматривать как разогрев, в результате чего PARITY не находится в . $AC^0$

Существуют также некоторые результаты и попытки доказательства нижних границ сложности доказательств с использованием нестандартных моделей (некоторые результаты Ajtai и Krajicek. См. «Форсирование со случайными переменными и сложность доказательства», предоставленные Cambridge Press, но также черновой вариант). доступно онлайн ). Основная идея состоит в том, чтобы построить нестандартную модель арифметики, в которой утверждение является ложным в модели (а не «верно, но без кратких доказательств»), а затем, исходя из свойств модели, сделать вывод, что соответствующая последовательность конечна утверждения не имеют доказательств полиномиального размера в некоторой системе доказательств.

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

Джошуа Грохов
источник

4

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

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

Денис
источник

Сведение пороговых вопросов к вопросам конечности

Ответы: