Редкие языки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема (Махэни); no sane person writes 'sparce' instead of 'sparse')
м (rollbackEdits.php mass rollback)
 
(не показана 1 промежуточная версия 1 участника)
(нет различий)

Текущая версия на 11:44, 1 сентября 2022

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

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

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