vs

В нашей недавней работе мы решили вычислительную проблему, возникшую в комбинаторном контексте, исходя из предположения, что , где - это -версия . Единственной найденной нами статьей о была статья Бейгеля-Бурмана-Фортнау 1998 года , в которой упоминается комплексный зоопарк . Мы понимаем, что можем взять версии задач (см. Этот вопрос ), но, возможно, многие из них на самом деле не являются полными в . $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ $\mathsf{\oplus{}EXP}$ $\mathsf{EXP}$ $\mathsf{\oplus{}P}$ $\mathsf{\oplus{}EXP}$ $\mathsf{NEXP}$ $\mathsf{\oplus{}EXP}$

ВОПРОС: Есть ли причины сложности полагать, что ? Существуют ли естественные комбинаторные задачи, полные в ? Есть ли какие-то ссылки, которые мы могли бы пропустить? $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ $\mathsf{\oplus{}EXP}$

cc.complexity-theory complexity-classes conditional-results structural-complexity Игорь Пак
источник

Я думаю, что паритетные версии, по крайней мере, некоторых неполных для NEXP задач были бы complete-полными по той же причине, например SUCCINCT 3SAT. Классы четности являются `` синтаксическими ', как и экзистенциальный недетерминизм, поэтому у вас есть те же стандартные методы для решения полных задач

Грег Куперберг

Спасибо, Грег. Я понимаю. Хотя не все проблемы будут работать, например, четкость количества трехцветных графов SUCCINCT проста.

Игорь Пак

Проблема в вашем примере с соотношением количества 3-х цветов (которое, конечно, делится на 6) ортогональна заданному вопросу о классах сложности уровня EXP. Вопрос заключается в том, есть ли сокращение, то есть сокращение, которое сохраняет число свидетелей. Это часто известно, но иногда нет. Например, в случае с 3-мя раскрасками есть красивая бумага от Barbanchon (которую я недавно видел по своим собственным причинам), которая дает экономное сокращение от SAT, за исключением фактора 6.

Грег Куперберг

Ах, верно. Интересный. Нашел его: Régis Barbanchon, Об уникальном графе 3-окрашиваемости и экономном сокращении на плоскости (2004).

Игорь Пак

@GregKuperberg: похоже на ответ! Обратите внимание, что Valiant показал ( people.seas.harvard.edu/~valiant/focs06.pdf ), что даже является -complete.

\oplus 2 S A T

$\oplus 2SAT$

\oplus P

$\oplus \mathsf{P}$

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

Ответы:

С точки зрения сложности (а не полных задач): Теорема Хартманиса-Иммермана-Севельсона также должна работать в этом контексте, а именно: если существует полиномиально разреженное множество в . Учитывая, как далеко друг от друга мы думаем, и - например, Тода показал, что - это будет быть весьма удивительным, если бы в их разнице не было редких множеств. $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ $\oplus \mathsf{P} \backslash \mathsf{P}$ $\mathsf{P}$ $\oplus \mathsf{P}$ $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$

Точнее, если бы в их разнице не было разреженных множеств, было бы сказано, что для каждого верификатора , если число строк длины с нечетным числом свидетелей ограничено , тогда проблема [определения наличия нечетного числа свидетелей] должна быть в . Это кажется поразительным и маловероятным фактом. $\mathsf{NP}$ $n$ $n^{O(1)}$ $\mathsf{P}$

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

Я не понимаю последнюю часть. Любая проблема NP может быть выражена таким образом, чтобы число свидетелей всегда было четным, а 0, безусловно, ограничено полиномиально, поэтому вы фактически говорите, что P = NP, и я не вижу, как это следует.

Эмиль Йержабек поддерживает Монику

@ Эмиль, «верификатор» в скобках, кажется, проясняет, что имел в виду Джош.

Каве

@ EmilJeřábek: Действительно, Kaveh получил это точно. Как вы указали, утверждение действительно работает, только если вы говорите о каждом верификаторе NP, а не о каждой проблеме NP. Я отредактировал ответ так, что это уже не комментарий в скобках.

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

Извините, но это ничего не прояснило. Если заявление относится ко всем верификаторам, оно, в частности, относится к верификаторам, которые всегда имеют четное число свидетелей.

Эмиль Йержабек поддерживает Монику

@ EmilJeřábek: Ах да, я вижу ваше замешательство сейчас (я думаю). Уточнено. Результат кажется мне немного менее поразительным, но ненамного (особенно в свете результатов Тоды).

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