Редкие языки
Язык - редкий, если .
Теорема (Махэни)
- Эта страница последний раз была отредактирована 1 сентября 2022 в 11:44.
Язык [math]L[/math] - редкий, если [math] | L \cap \Sigma^n | \le p(n)[/math].
[math]NP \le L,~L\in Sparse \Rightarrow P = NP[/math]
