Редкие языки

Материал из Викиконспекты
Версия от 22:21, 2 июня 2010; 192.168.0.2 (обсуждение) (Новая страница: «Язык <tex>L</tex> - редкий, если <tex> | L \cap \Sigma^n | \le p(n)</tex>. ==Теорема (Махэни)== <tex>NP \le L,~L\in Sparce \Rightarrow P …»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Редкие_языки&oldid=1390»