Псевдополиномиальное преобразование

В теории сложности вычислений псевдополиномиальное преобразование — это функция, которая отображает экземпляры одной сильно NP-полной задачи в другую и вычислима за псевдополиномиальное время . ^[1]

Определения

Максимальный числовой параметр

Некоторые вычислительные задачи параметризуются числами, величина которых экспоненциально превышает размер входных данных. Например, проблему проверки того, является ли число n простым, можно решить, просто проверив возможные множители от 2 до ${\sqrt {n}}$ в ${\sqrt {n}}-1$ делений, поэтому экспоненциально больше, чем входной размер $O(\log(n))$ . Предположим, что $L$ это кодировка вычислительной задачи $\Pi$ над алфавитом $\Sigma$ , затем

\operatorname {Num} _{\Pi }:\Sigma ^{*}\to \mathbb {N}

это функция, которая отображает $w_{I}\in \Sigma ^{*}$ , являющийся кодировкой экземпляра $I$ проблемы $\Pi$ , к максимальному численному параметру $I$ .

Псевдополиномиальное преобразование

Предположим, что $\Pi _{1}$ и $\Pi _{2}$ проблемы с решением, $L_{1}$ и $L_{2}$ их кодировки соответственно $\Sigma _{1}$ и $\Sigma _{2}$ алфавиты.

Псевдополиномиальное преобразование из $\Pi _{1}$ к $\Pi _{2}$ это функция $f:\Sigma _{1}\to \Sigma _{2}$ такой, что

$\forall w\in \Sigma _{1}\quad w\in L_{1}\iff f(w)\in L_{2}$
$\forall w\in \Sigma _{1}\quad f(w)$ может быть вычислено за полиномиальное время от двух переменных $\operatorname {Num} _{\Pi _{1}}(w)$ и $|w|$
$\exists Q_{A}\in \mathbb {N} [X]\quad \forall w\in \Sigma _{1}\quad |w|\leq Q_{A}(|f(w)|)$
$\exists Q_{B}\in \mathbb {N} [X,Y]\quad \forall w\in \Sigma _{1}\quad \operatorname {Num} _{\Pi _{2}}(f(w))\leq Q_{B}(\operatorname {Num} _{\Pi _{1}}(w),|w|)$

Интуитивно, (1) позволяет рассуждать о случаях $\Pi _{1}$ с точки зрения случаев $\Pi _{2}$ (и обратно), (2) гарантирует, что решение $L_{1}$ используя преобразование и псевдополиномиальный решатель для $L_{2}$ является псевдополиномиальным, (3) обеспечивает, что $f$ растет достаточно быстро, так что $L_{2}$ должен иметь псевдополиномиальный решатель, и (4) требует, чтобы подзадача $L_{1}$ что свидетельствует о ее сильной NP-полноте (т. е. все экземпляры имеют числовые параметры, ограниченные полиномом по размеру входных данных, а подзадача сама является NP-полной), отображается в подзадачу $L_{2}$ экземпляры которого также имеют числовые параметры, ограниченные полиномом входного размера.

Доказательство сильной NP-полноты

Следующая лемма позволяет вывести сильную NP-полноту из существования преобразования:

Если $\Pi _{1}$ является сильно NP-полной задачей решения, $\Pi _{2}$ является проблемой решения в NP, и существует псевдополиномиальное преобразование из $\Pi _{1}$ к $\Pi _{2}$ , затем $\Pi _{2}$ сильно NP-полна

Доказательство леммы

Предположим, что $\Pi _{1}$ представляет собой сильно NP-полную задачу принятия решений, кодируемую $L_{1}$ над $\Sigma _{1}$ алфавит и $\Pi _{2}$ - это проблема принятия решений в NP, закодированная $L_{2}$ над $\Sigma _{2}$ алфавит.

Позволять $f:L_{1}\to L_{2}$ быть псевдополиномиальным преобразованием из $\Pi _{1}$ к $\Pi _{2}$ с $Q_{A}$ , $Q_{B}$ как указано в определении.

По определению сильной NP-полноты существует полином $P\in \mathbb {N} [X]$ такой, что $L_{1/P}=\{w\in L_{1}:\operatorname {Num} _{\Pi _{1}}(w)\leq P(|w|)\}$ является NP-полной.