Просмотр исходного текста страницы Категория:Предложенные студентами задачи/Если существует унарный NP-полный язык, то P=NP/Решение Иноземцев

<latex>
Пусть $L$ - унарный NP-полный язык. Следовательно $SAT \leq_{p} L$. Пусть $A$ - соответствующая сводимость, работающая за время $p(n)$. 

Приведем алгоритм, который решает SAT за полиномиальное время. Тогда P=NP.\\

\\

\textbf{Функция} CheckSAT

Вход: формула $\phi$ (зависящая от переменных и констант)

Выход: 1, если выполнима, иначе - 0

Вспомогательные данные: таблица T, в которой $T(k)=1$, если $1^k \in L$, $T(k) = 0$, если $T(k) \notin L$, $T(k)=?$, если принадлежность к $L$ неизвестна.

(эта таблица имеет длину $p(|\phi|)$, одна и та же для всех рекурсивных вызовов функции, изначально заполнена вопросами)\\

$\textbf{Если } \phi \text{ не содержит переменных, то вычислить ее и вернуть вычисленное значение}$


$\textbf{Иначе }$


    \quad$ str=A(\phi)$


    \quad\underline{если} str содержит нули, то вернуть 0


    \quad\underline{иначе}, если $str=1^k$ и $T(k)\not= ?$, вернуть $T(k)


    \quad\underline{иначе}

        \qquad$p$ - первая переменная, существенно входящая в $\phi$.

        \qquad$\phi_0 = \phi|_{p=0}$

        \qquad\textit{если} $CheckSAT(\phi_0) = 1$, то $T(k) = 1$ и возвращаем 1

        \qquad\textit{если} $T(k) \not= ?$, то возвращаем $T(k)$.

        \qquad$\phi_1 = \phi|_{p=1}$

        \qquad$T(k) = CheckSAT(\phi_1}

        \qquad возвращаем $T(k)$\\




Покажем, что приведенный алгоритм корректен.

По свойству сводимости $\phi\in SAT \iff A(\phi)\in L$$. Если $A(\phi)$ не имеет вид $1^k$, то $A(\phi)\notin L$ и поэтому $\phi \notin SAT$. Если $A(\phi)=1^k$, то если $T(k)$ определено, то $T(k)=1\iff 1^k\in L \iff \phi\in SAT$. Если $T(k)$ не определено, пользуемся тем, что $\phi$ выполнима в том и только том случае, когда выполнима одна из формул $\phi|_{p=0}$ или $\phi|_{p=1}$. Поэтому рекурсивный вывод с $\phi|_{p=0}$ и $\phi|_{p=1}$ дает корректный ответ в виде дизъюнкции.

Докажем, что время работы полиномиальное. В начале работы в таблице $T$ содержится полиномиальное количество вопросительных знаков. Каждый запуск функции заменяет один вопросительный знак на 1 или 0. Если на некотором нижнем уровне рекурсии бы получен результат, запрошенный на верхнем уровне, то благодарая проверке на равенство $T(k)$ вопросительному знаку не будем совершен второй рекурсивный вызов. Следовательно, дерево рекурсивных вызовов будет иметь не более $p(n)$ точек бинарного ветвления. Т.е. в нем будет не больше $p(n)+1$ листьев и не больше $n(p(n)+1)$ вершин. Т.е. совершается не более $n(p(n)+1)$ рекурсивных вызовов, каждый из них полиномиален, поэтому весь алгоритм тоже полиномиален.