Свойство класса сложности P

Question

Я читаю книгу < < Введение в алгоритмы > >, третье издание. Существует доказательство теоремы 34,2 (Page 1059):

Поскольку класс языков решил алгоритмами полиномиальное время является подмножеством класса языков, принятого полиномиальное время алгоритмы, нам нужно только показывают, что если L принимается алгоритмом полиномиального времени, то он определяется алгоритмом полиномиального времени . Пусть Ь язык принял некоторым полиномиально алгоритм А ... (доказательство опущено) ... и, таким образом, А является полиномиальное время алгоритм, который решает L.

Я думаю, что это означает, что если есть два набора A и B, а A - подмножество B и элемент x∈A, это доказывает x∈B.

Кроме того, я понимаю, что «класс языков, определяемый полиномиально-временными алгоритмами, является подмножеством класса языков, принятого полиномиально-временными алгоритмами». Так что это доказательство меня смущает ...

Answer 1

В теории сложности вычислений, P, также известный как PTIME или DTIME (п^O (1)), является одним из основных классов сложности. Он содержит все решения, которые могут быть решены с помощью детерминированной машины Тьюринга с использованием полиномиального количества времени вычисления или полиномиального времени.

Источник: Wikipedia:P(Complexity)