Список теорем о том, что P не равен NP тогда и только тогда, когда

18

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

cc.complexity-theory big-list p-vs-np Тайфун Пей
источник
15
Это было бы постоянной долей всех документов сложности!
MCH
5
Я бы сказал: «список условий, подразумевающих P? NP», поскольку не все эти теоремы «тогда и только тогда». Кроме того, я думаю, что люди больше заинтересованы - в общем - в знании того, как доказать P? NP, доказывая что-то другое, чем в перечислении многих последствий этого результата, тема, которая широко обсуждалась в других местах.
Janoma
2
@Janoma: если вы хотите ограничить себя последствиями, то список будет действительно огромным, учитывая огромное количество результатов в форме: «Если P! = NP, то проблема X не может быть решена точно / приблизительно в пределах постоянного фактора в полиномиальное время ". Вопрос должен быть гораздо более сфокусированным или лучше сформулированным, если мы хотим этого избежать.
Энтони Лабарр
4
@Janoma: Это не решает обоснованную проблему Энтони. Гипотезы, которые подразумевают P = NP, являются просто отрицанием последствий P = NP, а гипотезы, которые подразумевают P = NP, являются отрицанием последствий P = NP. Если SAT разрешимо за полиномиальное время, то P = NP. Если Max3SAT аппроксимируется за полиномиальное время с постоянным коэффициентом менее 8/7, то P = NP. И так далее.
Tsuyoshi Ito
7
@Janoma: «Если X, то P = NP» совпадает с «Если P" NP, то не-X ».
Джеффс

Ответы:

11

Вот один из них:

Теорема Махани: разреженного NP-полного множества не существует тогда и только тогда, когда (при редукции Карпа).P≠NP

Еще один:

тогда и только тогда, когда P ≠ P HP≠NPP≠PH

Мухаммед Аль-Туркистани
источник
Может быть , это просто: тогда и только тогда , когда F P ≠ F N P . п≠NпFп≠FNп
Мухаммед Аль-Туркистани
11

тогда и только тогда, когда существуют односторонние функции в худшем случае.п≠Nп

Ссылка:

Алан Л. Сельман. Обзор односторонних функций в теории сложности. Математическая теория систем, 25 (3): 203–221, 1992.

Мухаммед Аль-Туркистани
источник
1
ссылка была бы хороша
vzn
Вы уверены? Я не слышал о наихудшем OWFs раньше, но из примечаний здесь , похоже , их существование эквивалентно . Впп≠Nп
Гек Беннетт
Да, я уверен. :) Смотрите ссылку.
Мохаммед Аль-Туркистани,
8

Вот результат теории описательной сложности:

тогда и только тогда, когда какое-либо свойство второго порядка не может быть выражено с использованием логики первого порядка плюс наименьшая фиксированная точка.п≠Nп

Ссылка: Immerman, Языки, которые захватывают классы сложности

Мухаммед Аль-Туркистани
источник
... на заказанные структуры. В противном случае мы безоговорочно знаем, что такие свойства существуют.
Эмиль Йержабек поддерживает Монику
@ EmilJeřábek да, на упорядоченных структурах, как это неявно предполагалось Иммерманом в статье выше.
Мухаммед Аль-Туркистани
7

Теорема Ладнера может быть сформулирована как:

том и только в том случае, если в N P - P существует неполное множество.п≠NпNп-п

Неполный набор - это набор, который не является полным для при многократном сокращении времени за полином.Nп

Ссылка

Теория сложности и криптология: введение в криптосложность Йорг Роте, стр. 106

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