Редкие языки — различия между версиями
(Новая страница: «Язык <tex>L</tex> - редкий, если <tex> | L \cap \Sigma^n | \le p(n)</tex>. ==Теорема (Махэни)== <tex>NP \le L,~L\in Sparce \Rightarrow P …») |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 2: | Строка 2: | ||
==Теорема (Махэни)== | ==Теорема (Махэни)== | ||
| − | <tex>NP \le L,~L\in | + | <tex>NP \le L,~L\in Sparse \Rightarrow P = NP</tex> |
Текущая версия на 11:44, 1 сентября 2022
Язык - редкий, если .
Теорема (Махэни)
