Проблемы за пределами P, которые не являются P-hard

Читая ответ Питера Шора и предыдущий вопрос Адама Крума, я понял, что у меня есть некоторые неправильные представления о том, что значит быть -hard. $\mathsf{P}$

Проблема -hard, если любая проблема в сводится к ней с помощью (или если вы предпочитаете ) сокращений. Проблема находится вне если не существует алгоритма полиномиального времени для ее решения. Это означает, что должны быть проблемы, которые находятся за пределами но не являются -hard. Если мы предположим, что FACTORING находится за пределами , то ответ Питера Шора предполагает, что FACTORING может быть такой проблемой. $\mathsf{P}$ $\mathsf{P}$ $\mathsf{L}$ $\mathsf{NC}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$

Существуют ли какие-либо известные проблемы (естественные или искусственные), которые, как известно, лежат за пределами но не являются -hard? Как насчет допущений, более слабых, чем допущение факторинга? Есть ли название для этого класса сложности? $\mathsf{P}$ $\mathsf{P}$

cc.complexity-theory complexity-classes Артем Казнатчеев
источник

Ответы:

Если $\mathsf{P} \neq \mathsf{L}$ то никакое разреженное множество (даже невычислимое) не может быть $\mathsf{P\text{-}hard}$ .

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

Кава
источник

некоторые диаграммы Эйлера, которые я видел для классов сложности, также породили для меня второе заблуждение, которое, как мне кажется, вызвало у меня замешательство в отношении X-твердости.

Артем Казнатчеев

@ Артем, да, это тоже фактор. Вот что я делаю в классе: я упоминаю несопоставимость

\mod p

$\mod p$

присокращениях

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

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Каве

общая часть заказа у меня гораздо меньше проблем. В частности, я думаю, что NP и coNP достаточно хороши, чтобы показать, что мы не должны думать о классах сложности, имеющих общий порядок.

Артем Казнатчеев

@ Артем, хорошая мысль (хотя мы не можем доказать, что они разные). Я думаю, что одной из причин терминологии является отсутствие разумных нижних границ, у нас нет хорошего нижнего предела для SAT, но мы думаем, что его трудно решить, потому что он универсален, но слово «универсальный» не дать такое же чувство трудности, как и «трудный», особенно для неспециалистов. Но это создает проблему, потому что, хотя можно утверждать, что универсальность проблемы подразумевает, что проблему трудно решить, сложность решения проблемы не означает, что проблема универсальна.

Каве

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

Каве

Я думаю, что вы можете построить множество не в , которое не является трудным по аргументу в стиле Ладнера. Вот конкретный пример. $P$ $P$

В своей статье «Единообразный подход к получению диагональных множеств в классах сложности» (Theor. Comp. Sci. 18, 1982) Шенинг доказывает следующее:

Теорема Предположим, что , , и являются рекурсивно представимыми классами сложности и замкнуты при конечных вариациях. Тогда существует множество такое, что , , и если и не тривиальны (пустое множество или все строки), то является множителем много-один, приводимым к . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Чтобы применить это, установите чтобы быть пустым набором, и чтобы быть -завершенным при сокращениях polytime, установите быть набором жестких наборов, которые находятся в , установите , Пустое множество не может быть -hard (определение -hardness для языка требует, чтобы в нем был хотя бы один экземпляр, а один - нет). определенно не в . и $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ может быть проверен на соответствие вышеуказанным условиям (аналогично тому, как это делает Шеннинг для -полных множеств; см. Такжеэтот связанный вопрос). Таким образоммы получаем , который не является -Жесткой проблемы в , и чтоне в . Но поскольку и нетривиально,множество, один приводимым к -полное множество, так что в . Поэтому, в частности, $C_2$ $NP$ $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ не может быть жесткий либо. $P$

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

Райан Уильямс
источник

Мне нравится , как это проходит , даже если

. Если я что-то не так понял.

L = P

$L = P$

Артем Казнатчеев

@Artem: Если вы рассматриваете жесткость при сводимости лог-пространства, то каждый нетривиальный язык является L-трудным. Следовательно, если L = P, то нет языков за пределами P, которые являются P-hard при сводимости лог-пространства.

Цуёси Ито

Другой способ генерировать задачи, которые находятся вне P, но не P-hard, - это взять полные задачи для классов, несопоставимых с P. Скажем, класс X несопоставим с P в том смысле, что ни один из них не является подмножеством другого. Тогда X-полная задача обязательно находится вне P (в противном случае P будет включать в себя X) и не является P-трудной (в противном случае X будет включать в себя P).

Я пытался представить некоторые классы, несопоставимые с P, но P - довольно надежный класс, поэтому таких классов не так уж много. Например, RNC и QNC могут быть несопоставимы с P. DSPACE ( ) также могут быть несопоставимы с P. PolyL несопоставимы с P, но не имеют полных проблем при сокращении пространства журналов. $\log^2$

Робин Котари
источник

На мой взгляд, это почти один и тот же вопрос, сформулированный по-разному, и это не обязательно способ ответить на вопрос. На самом деле, язык A не является ни P, ни P-hard тогда и только тогда, когда класс языков, сводимых к A, несопоставим с P (возьмите ваше любимое понятие сводимости). Что касается текущего вопроса, я думаю, что он более полезен в противоположном направлении; то есть это еще один способ интерпретации ответов на текущий вопрос.

Цуёси Ито