Редкие языки — различия между версиями
(Новая страница: «Язык <tex>L</tex> - редкий, если <tex> | L \cap \Sigma^n | \le p(n)</tex>. ==Теорема (Махэни)== <tex>NP \le L,~L\in Sparce \Rightarrow P …») |
м (→Теорема (Махэни); no sane person writes 'sparce' instead of 'sparse') |
||
| Строка 2: | Строка 2: | ||
==Теорема (Махэни)== | ==Теорема (Махэни)== | ||
| − | <tex>NP \le L,~L\in | + | <tex>NP \le L,~L\in Sparse \Rightarrow P = NP</tex> |
Версия 20:52, 25 мая 2021
Язык - редкий, если .
Теорема (Махэни)
