vs

15

В нашей недавней работе мы решили вычислительную проблему, возникшую в комбинаторном контексте, исходя из предположения, что , где - это -версия . Единственной найденной нами статьей о была статья Бейгеля-Бурмана-Фортнау 1998 года , в которой упоминается комплексный зоопарк . Мы понимаем, что можем взять версии задач (см. Этот вопрос ), но, возможно, многие из них на самом деле не являются полными в . EXPEXPEXPEXPPEXPNEXPEXP

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

Игорь Пак
источник
6
Я думаю, что паритетные версии, по крайней мере, некоторых неполных для NEXP задач были бы complete-полными по той же причине, например SUCCINCT 3SAT. Классы четности являются `` синтаксическими ', как и экзистенциальный недетерминизм, поэтому у вас есть те же стандартные методы для решения полных задач
Грег Куперберг
Спасибо, Грег. Я понимаю. Хотя не все проблемы будут работать, например, четкость количества трехцветных графов SUCCINCT проста.
Игорь Пак
2
Проблема в вашем примере с соотношением количества 3-х цветов (которое, конечно, делится на 6) ортогональна заданному вопросу о классах сложности уровня EXP. Вопрос заключается в том, есть ли сокращение, то есть сокращение, которое сохраняет число свидетелей. Это часто известно, но иногда нет. Например, в случае с 3-мя раскрасками есть красивая бумага от Barbanchon (которую я недавно видел по своим собственным причинам), которая дает экономное сокращение от SAT, за исключением фактора 6.
Грег Куперберг
2
Ах, верно. Интересный. Нашел его: Régis Barbanchon, Об уникальном графе 3-окрашиваемости и экономном сокращении на плоскости (2004).
Игорь Пак
3
@GregKuperberg: похоже на ответ! Обратите внимание, что Valiant показал ( people.seas.harvard.edu/~valiant/focs06.pdf ), что даже является -complete. 2SATP
Джошуа Грохов

Ответы:

14

С точки зрения сложности (а не полных задач): Теорема Хартманиса-Иммермана-Севельсона также должна работать в этом контексте, а именно: если существует полиномиально разреженное множество в . Учитывая, как далеко друг от друга мы думаем, и - например, Тода показал, что - это будет быть весьма удивительным, если бы в их разнице не было редких множеств.EXPEXPPPPPPHBPPP

Точнее, если бы в их разнице не было разреженных множеств, было бы сказано, что для каждого верификатора , если число строк длины с нечетным числом свидетелей ограничено , тогда проблема [определения наличия нечетного числа свидетелей] должна быть в . Это кажется поразительным и маловероятным фактом. н н О ( 1 ) ПNPnnO(1)P

Джошуа Грохов
источник
Я не понимаю последнюю часть. Любая проблема NP может быть выражена таким образом, чтобы число свидетелей всегда было четным, а 0, безусловно, ограничено полиномиально, поэтому вы фактически говорите, что P = NP, и я не вижу, как это следует.
Эмиль Йержабек поддерживает Монику
1
@ Эмиль, «верификатор» в скобках, кажется, проясняет, что имел в виду Джош.
Каве
@ EmilJeřábek: Действительно, Kaveh получил это точно. Как вы указали, утверждение действительно работает, только если вы говорите о каждом верификаторе NP, а не о каждой проблеме NP. Я отредактировал ответ так, что это уже не комментарий в скобках.
Джошуа Грохов
Извините, но это ничего не прояснило. Если заявление относится ко всем верификаторам, оно, в частности, относится к верификаторам, которые всегда имеют четное число свидетелей.
Эмиль Йержабек поддерживает Монику
1
@ EmilJeřábek: Ах да, я вижу ваше замешательство сейчас (я думаю). Уточнено. Результат кажется мне немного менее поразительным, но ненамного (особенно в свете результатов Тоды).
Джошуа Грохов