141
правка
Изменения
м
Ссылка на сведение ещё одна
Язык <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> памяти).
}}
