Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 8.4. Up: 8. Класс IP Previous: 8.2. Определение класса IP Contents: Содержание

8.3.

Определение $\ensuremath{\mathrm {IP}}$ похоже на уголовно-процессуальное определение класса $\ensuremath{\mathrm{PSPACE}}$ . И доказательство $\ensuremath{\mathrm {IP}}\subseteq\ensuremath{\mathrm{PSPACE}}$ напоминает ту часть доказательства теоремы 5, в которой строится алгоритм определения выигрышной стратегии, использующий полиномиально ограниченную память.

Пусть $f(x)\in\ensuremath{\mathrm {IP}}$ . Снова по индукции определяется набор машин Тьюринга для $k=0,\dots,s(\vert x\vert)$ .

Каждая по заданному началу диалога $x,r_1,p_1,\dots,r_k,p_k$ длины между Исполнителем и Советником оценивает вероятность ответа при продолжении диалога. Последняя в этом ряду машина $M_{s(\vert x\vert)}$ имитирует работу Исполнителя, вычисляет функцию $V(x,r_1,p_1\dots)$ и сообщает в качестве ответа ее значение. Машина перебирает все возможные варианты -го сообщения и консультируется с $M_{k+1}$ по поводу окончательных результатов. Если слово за Советником, то оценка - максимум оценок $M_{k+1}$ по всем возможным вариантам сообщения Советника. Если слово за Исполнителем, то оценка $M_{k}$ равна среднему арифметическому оценок $M_{k+1}$ по всем (это формула полной вероятности).

Алгоритм вычисления на полиномиальной памяти запускает и выдает в качестве результата 1, если оценка больше , и 0, если оценка меньше .

МЦНМО

Написать комментарий