403
правки
Изменения
это вообще кто-нибудь проверял?
<tex>check(\phi, i)</tex>:
'''if''' <tex>\phi=0</tex>
'''returnexit''' 0
'''if''' <tex>\phi=1</tex>
'''return''' 1
'''exit''' <tex>0</tex>
'''return''' <tex>memo[f(\phi)]</tex>
[[Файл:Berman-Fortune.png|thumb|upright=2.0|Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу ''memo[j]''. В красных узлах условие ''(1)'' ложно, в желтых {{---}} истинно.]]
Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.
Рассмотрим произвольный элемент <tex>memo[ij]</tex>. Найдем, сколько раз условие <tex>(1)</tex> в ходе выполнения программы является ложным при обращении к элементу <tex>memo[ij]</tex>. Найдем в дереве такой узел, в котором есть обращение к <tex>memo[ij]</tex>, а в его поддереве обращений к этому элементу нет, причем <tex>memo[ij] = -1</tex>. До этого момента количество обращений к <tex>memo[ij]</tex> не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома <tex>p'(n)</tex>. После этого момента условие <tex>(1)</tex> будет принимать истинное значение при обращении к <tex>memo[ij]</tex>. Значит, в ходе выполнения программы условие <tex>(1)</tex> является ложным при обращении к <tex>memo[ij]</tex> не более <tex>p'(n)</tex> раз.
Так как всего в <tex>memo</tex> не более <tex>r(n)</tex> элементов, то суммарно за все время выполнения программы условие <tex>(1)</tex> принимает ложное значение не более <tex>p''(n) = r(n) \cdot p'(n)</tex> раз, то есть <tex>p''</tex> {{---}} полином. Отсюда следует, что присваивание <tex>(2)</tex> выполняется не более <tex>p''(n)</tex> раз, а значит в дереве не более <tex>p''(n)</tex> внутренних вершин. Значит всего в дереве не более <tex>2 \cdot p''(n) + 1</tex> вершин, то есть данная программа работает за полиномиальное время.
== См. также ==
*[[Класс P]]
*[[Недетерминированные вычисления. Классы NP и Σ₁]]
[[Категория: Теория сложности]]
