Редукция Карпа идентична редукции Левина

Определение: уменьшение Карпа

Язык является приводимым по Карпу к языку если существует вычислимая функция за полиномиальное время такая, что для каждого , тогда и только тогда , когда . $A$ $B$ $f:\{0,1\}^*\rightarrow\{0,1\}^*$ $x$ $x\in A$ $f(x)\in B$

Определение: Левин Сокращение

Задача поиска сводится по Левину к задаче поиска если существует функция полиномиального времени, при которой Карп в и существуют вычислимые функции полиномиального времени и такие что $V_A$ $V_B$ $f$ $L(V_A)$ $L(V_B)$ $g$ $h$

$\langle x, y \rangle \in V_A \implies \langle f(x), g(x,y) \rangle \in V_B$ ,
$\langle f(x), z \rangle \in V_B \implies \langle x, h(x,z) \rangle \in V_A$

Эти сокращения эквивалентны?

Я думаю, что два определения эквивалентны. Для любых двух языках и , если является Карп сводится к , то является Левин сводится к . $\mathsf{NP}$ $A$ $B$ $A$ $B$ $A$ $B$

Вот мое доказательство:

Пусть и произвольные экземпляры , а в том , что из . Пусть и являются испытатели и . Пусть и - произвольные сертификаты и соответствии с . Позвольте быть тем из согласно . $x$ $\overline{x}$ $A$ $x'$ $B$ $V_A$ $V_B$ $A$ $B$ $y$ $\overline{y}$ $x$ $\overline{x}$ $V_A$ $z$ $x'$ $V_B$

новые верификаторы и с новыми сертификатами и : $V'_A$ $V'_B$ $y'$ $z'$

$V'_A(x,y'):$

$y'=\langle 0,\overline{x},\overline{y}\rangle$ : если , отклонить. В противном случае выведите . $f(x)\ne f(\overline{x})$ $V_A(\overline{x},\overline{y})$
$y'=\langle 1,z\rangle$ : вывод . $V_B(f(x),z)$

$V'_B(x',z'):$

$z'=\langle 0,z\rangle$ : вывод . $V_B(x',z)$
$z'=\langle 1,x,y\rangle$ : если , отклонить. В противном случае выведите . $x'\ne f(x)$ $V_A(x,y)$

Вычисляемые функции полиномиального времени и определены следующим образом: $g$ $h$

$g(x,y')$

$y'=\langle 0,\overline{x},\overline{y}\rangle$ : Выведите . $\langle 1,\overline{x},\overline{y}\rangle$
$y'=\langle 1,z\rangle$ : Выведите . $\langle 0,z\rangle$

$h(x',z')$

$z'=\langle 0,z\rangle$ : Выведите . $\langle 1,z\rangle$
$z'=\langle 1,x,y\rangle$ : Выведите . $\langle 0,x,y\rangle$

Пусть будет набором всех сертификатов согласно а будет набором всех сертификатов согласно . Тогда набор всех сертификатов соответствии с равен такой, что , и набор всех сертификатов согласно равен , так что . $Y_x$ $x$ $V_A$ $Z_{x'}$ $x'$ $V_B$ $x$ $V'_A$ $0\overline{x}Y_\overline{x}+1Z_{f(x)}$ $f(x)=f(\overline{x})$ $x'$ $V'_B$ $0Z_{x'}+1\overline{x}Y_\overline{x}$ $x'=f(\overline{x})$

(Это получено из принимающего языка и .) $V'_A$ $V'_B$

Теперь пусть , остальная часть легко проверяется. $x'=f(x)$

complexity-theory reductions check-my-proof куб.см
источник

Прежде чем доказывать свою претензию, вы должны определить, что это означает, когда язык Левина сводится к другому.

Tsuyoshi Ito

Ответы:

Нет. Сначала обратите внимание, что сокращение Левина имеет смысл только в отношении классов, сертификат которых имеет значение, например, то время как сокращение Карпа является общим. Слово «сертификат» для проблемы имеет смысл только тогда, когда верификатор исправлен. Сокращение Левина предполагает, что верификаторы исправлены. Вы не можете изменить верификаторы. (В дальнейшем я предполагаю, что верификаторы сертификатов исправлены в соответствии с требованиями определения Левина.) $\mathsf{NP}$

Во-вторых, сокращение Левина означает, что можно найти сертификат для одного из сертификата для другого. Это правда, что общеизвестные редукции Карпа между естественными проблемами оказываются редукцией Левина, но в целом это не обязательно должно быть.

Если мы можем свести случаи проблемы к проблеме это не значит, что у нас есть способ вычислить сертификат для одного из сертификата для другого. $A$ $B$

Чтобы это было правдой, нам необходим тот факт, что задача поиска сертификата, соответствующая проблеме решения, сводится за полиномиальное время к проблеме решения. Это верно для задач но, как известно, в общем случае верно даже для задач . $\mathsf{NP\text{-}complete}$ $\mathsf{NP}$

Кава
источник

Я согласен с вашей первой точкой зрения, что сокращение Карпа является более общим, чем сокращение Карпа. В соответствии с этим, я думаю, что моя проблема должна быть изменена следующим образом: «Пусть и - два языка в . Если сводится к Карпу к , то сводится к Левину к ». Однако я не согласен с другими вашими комментариями.

L_{1}

$L_1$

L_{2}

$L_2$

N P

$NP$

L_{1}

$L_1$

L_{2}

$L_2$

L_{1}

$L_1$

L_{2}

$L_2$

Копия

В моем доказательстве сначала пусть и - произвольные два таких языка. Так как они в , есть P TM и . Для каждого экземпляра набор всех сертификатов для . Точно так же мы определяем для . Поскольку сводится по Карпу к , существует такое как определено.

L_{1}

$L_1$

L_{2}

$L_2$

N P

$NP$

M_{1}

$M_1$

M_{2}

$M_2$

x \in L_{1}

$x\in L_1$

Y_{x}

$Y_x$

T M_{1}

$TM_1$

Z_{x^{'}}

$Z_{x'}$

x^{'} \in L_{2}

$x'\in L_2$

L_{1}

$L_1$

L_{2}

$L_2$

f

$f$

Копия

Теперь мы построили новые и . Для каждого экземпляра новый набор всех сертификатов , в то время как для каждого экземпляра новый набор всех сертификатов . (Здесь мы используем регулярные выражения) Это допустимые и все сертификаты для и . Кстати, есть функции P и как определено, преобразовывающие все возможные сертификаты из одной проблемы в другую.

M_{1}^{'}

$M_1'$

M_{2}^{'}

$M_2'$

x \in L_{1}

$x\in L_1$

0 Y_{x} + 1 Z_{f (x)}

$0Y_x+1Z_{f(x)}$

f (x) \in L_{2}

$f(x)\in L_2$

0 Z_{f (x)} + 1 x Y_{x}

$0Z_{f(x)}+1xY_x$

M_{1}^{'}

$M_1'$

M_{2}^{'}

$M_2'$

g

$g$

h

$h$

Копия

ps: нам не нужно давать преобразование из где нет такого, что , так как сокращения Карпа и Левина оба являются многозначными отображениями. Я думаю, что это может ответить на второй последний абзац.

x^{'} \in L_{2}

$x'\in L_2$

x \in L_{1}

$x\in L_1$

x^{'} = f (x)

$x'=f(x)$

Копия

@cc, кажется, что вы все еще думаете, что вы можете изменить верификаторы, но вы не можете, определение редукции Левина предназначено для задач поиска, т.е. верификаторы исправлены.

Каве

Быстрый контрпример для вашего доказательства: предположим, что , , и является действительным сертификатом для но не для $x_1, x_2 \in L_1$ $f(x_1) = f(x_2) \in L_2$ $w$ $x_1$ $x_2$

$M_1'(x_1,\langle 0,w \rangle)= M_1(x_1,w)=1$

$M_1'(x_2,\langle 0,w \rangle)= M_1(x_2,w)=0$

По определению $g(x_1,\langle 0,w \rangle) = \langle 1,x_1,w \rangle$

$f(x_1)=f(x_2)$ так , так является действительный сертификат для но $M'_2(f(x_2),\langle 1,x_1, w \rangle)) = M_1(x_1,w) = 1$ $\langle 1,x_1, w \rangle$ $f(x_2)$

$h(f(x_2), \langle 1,x_1, w \rangle) = \langle 0, w \rangle$ который не является действительным сертификатом для $x_2$

Вор
источник

Большое спасибо за указание на контрпример. Я изменил конструкцию, и я думаю, что она работает сейчас. Не могли бы вы взглянуть на это?

Копия