141
правка
Изменения
Добавил что-то по пункту "7" из требований АС
<tex>\mathrm{CFL} \subset \mathrm{TS}(n^3, n^2) \subset \mathrm{P}</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}
== Пример P-полной задачи ==
{{Определение
|definition=
<tex>CIRCVAL = \{\langle C, x_1,\ldots,x_n\rangle \bigm| C(x_1,\ldots,x_n) = 1\}</tex>, где <tex>C</tex> это логическая схема.
}}
{{Теорема
|statement =
<tex>CIRCVAL</tex> {{---}} <tex>\mathrm{P}</tex>-[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи#Определения трудных и полных задач|полная]] задача.
}}
