Изменения

Теорема Ладнера

27 байт добавлено, 12:06, 18 марта 2010

м

Нет описания правки

'''Теорема Ладнера''' (Ladner's Theorem) утверждает,

что если [[Класс P|P]] не совпадает с [[Класс NP|NP]], то существует язык <tex>L</tex>,

принадлежащий <tex>NP</tex>, но не являющийся полиномиальным и [[NP-полнота|NP-полным]].

109

правок