Чем питаются теоремы о дихотомии?

10

Хорошо известно , что некоторые классы NP -проблемы Have дихотомии теорем, которые гарантируют , что каждая задача в классе является либо NP -полное или находится в P . Наиболее известным таким результатом является теорема Шефера о дихотомии , а также ряд обобщений.

Насколько я понимаю, доказать эти теоремы дихотомии не очень легко. Интересно, есть ли какое-то относительно краткое объяснение того, почему некоторые классы имеют теоремы о дихотомии, а другие нет? Какая основная структура проблемы делает эти теоремы возможными? Или, возможно, нет такой четко понятной структуры, скорее в каждом случае остается загадкой, почему у класса есть или нет теорема о дихотомии?

cc.complexity-theory np descriptive-complexity Андрас Фараго
источник
2
Хороший вопрос Я думаю, что одна интуиция состоит в том, что мы ограничиваем проблемы классом, у которого есть хорошие описания.
Каве
5
Это не ответ, но, возможно, указывает, где ответ может (не) быть: если класс задач достаточно велик, чтобы включать в себя все (или даже просто определенное его подмножество), тогда Теорема будет применяться, и не будет дихотомии. Так что класс с дихотомией, по крайней мере, должен быть достаточно структурирован, чтобы избежать Ладнера ...NP
Джошуа Грохов
1
Дихотомии возникают, когда язык слишком груб, чтобы проводить тонкие различия.
Андрас Саламон

Ответы:

2

Для случая теоремы Шефера о дихотомии, неофициально, универсальная выразительная сила булевых формул CNF, построенных из нешеферовых логических отношений, стоит за дихотомией. Каждое логическое отношение определяется такой формулой с использованием экзистенциального квантификатора. Это формально утверждается в теореме Шефера о выразимости (теорема 2.5).

Мухаммед Аль-Туркистани
источник