Изменения

Перейти к: навигация, поиск

Класс P

382 байта добавлено, 18:12, 4 июня 2012
Пример P-полной задачи: Определение P-полноты, всё же
}}
== Пример P-полной полные задачи =={{Определение|definition=Язык <tex>X</tex> является <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полным]], если:# <tex>X \in \mathrm{P}</tex>;# <tex>\forall Y \in \mathrm{P} \Rightarrow Y \leq_L X</tex> (то есть любой язык из класса <tex>\mathrm{P}</tex> сводится к <tex>X</tex> с использованием <tex>O(log(n))</tex> памяти).}} 
{{Определение
|definition=
{{Теорема
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полная]] задача.
}}
141
правка

Навигация