Редкие языки

Материал из Викиконспекты
Версия от 20:52, 25 мая 2021; Breaker Zirconia (обсуждение | вклад) (Теорема (Махэни); no sane person writes 'sparce' instead of 'sparse')
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Теорема (Махэни)[править]

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