Редкие языки

Материал из Викиконспекты
Версия от 11:44, 1 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Язык [math]L[/math] - редкий, если [math] | L \cap \Sigma^n | \le p(n)[/math].

Теорема (Махэни)

[math]NP \le L,~L\in Sparse \Rightarrow P = NP[/math]

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Редкие_языки&oldid=84312»