KARPの減少は、レビンの減少と同じです

Question

定義：KARPの削減

言語$ a $は、多項式時間計算可能な関数がある場合、言語$ b $に削減可能です。 $ x $、$ x in A $の場合、$ f（x） in b $の場合にのみ。

定義：レビンの削減

検索の問題$ v_a $は検索問題に対してレビンを減らすことができます$ v_b $多項式時間関数$ f $がkarpが$ l（v_a）$を$ l（v_b）$に削減し、多項式時間計算可能関数$がありますG $と$ H $など

1. $ langle x、y rangle in v_a は langle f（x）、g（x、y） rangle in v_b $、

2. $ langle f（x）、z rangle in v_b は langle x、h（x、z） rangle in v_a $を暗示します

これらの削減は同等ですか？

---

2つの定義は同等だと思います。任意の2つの$ mathsf {np} $言語の場合、$ a $ aが$ b $に削減可能な場合、$ a $は$ b $に削減できます。

これが私の証拠です：

$ x $ and $ overline {x} $を$ a $の任意のインスタンスとし、$ x '$は$ b $です。 $ v_a $と$ v_b $が$ a $ and $ b $の検証剤であるとします。 $ y $および$ overline {y} $を$ x $および$ overline {x} $の任意の証明書とします。 $ z $と$ x '$の$ v_b $に従って。

新しい証明書$ v'_a $ and $ v'_b $を新しいVerifiers $ v'_a $および$ v'_b $を作成します$ y $および$ z '$：

$ v'_a（x、y '）：$

1. $ y '= langle 0、 overline {x}、 overline {y} rangle $：if $ f（x） ne f（ overline {x}）$、拒否。それ以外の場合は、出力$ v_a（ overline {x}、 overline {y}）$。
2. $ y '= langle 1、z rangle $：出力$ v_b（f（x）、z）$。

$ v'_b（x '、z'）：$

1. $ z '= langle 0、z rangle $：output $ v_b（x'、z）$。

2. $ z '= langle 1、x、y rangle $：if $ x' ne f（x）$、拒否。それ以外の場合、出力$ v_a（x、y）$。

多項式時間計算可能機能$ g $および$ h $は、以下のように定義されます。

$ g（x、y '）$

1. $ y '= langle 0、 overline {x}、 overline {y} rangle $：output $ langle 1、 overline {x}、 overline {y} rangle $。

2. $ y '= langle 1、z rangle $：出力$ langle 0、z rangle $。

$ h（x '、z'）$

1. $ z '= langle 0、z rangle $：output $ langle 1、z rangle $。

2. $ z '= langle 1、x、y rangle $：出力$ langle 0、x、y rangle $。

$ y_x $を$ v_a $および$ z_ {x '} $に従って$ x $のすべての証明書のセットとし、$ v_b $に従って$ x' $のすべての証明書のセットとします。次に、$ v'_a $に従って$ x $のすべての証明書のセットは、$ 0 overline {x} y_ overline {x}+1z_ {f（x）} $です。オーバーライン{x}）$、および$ v'_b $に従って$ x '$のすべての証明書のセットは、$ 0Z_ {x'}+1 overline {x} y_ overline {x} $です。 '= f（ overline {x}）$。

（これは、$ v'_a $と$ v'_b $の受け入れ言語から派生しています。）

ここで、$ x '= f（x）$とし、残りの部分は簡単に確認できます。

Answer 1

いいえ。最初に、レビンの削減は、どの証明書に意味があるかについてのみ理にかなっていることに注意してください。問題の「証明書」という言葉は、検証剤が修正された場合にのみ理にかなっています。レビンの削減は、検証剤が固定されていると想定しています。検証剤を変更することはできません。 （以下では、レビンの削減を定義することにより、証明書の検証剤が必要に応じて修正されていると仮定します。）

第二に、レビンの削減とは、一方の証明書を他方の証明書から証明書の証明書を見つけることができることを意味します。自然な問題の間のよく知られているKARPの削減がレビンの削減であることが判明したことは事実ですが、これは一般的に真実である必要はありません。

問題のインスタンスを減らすことができれば、$ a $から問題$ b $を削減できたとしても、他方の証明書から証明書を計算する方法があるわけではありません。

これが真実であるためには、決定問題に対応する証明書検索問題が決定問題に還元できる多項式時間であるという事実が必要です。これは$ mathsf {np text { - } complete} $の問題に当てはまりますが、$ mathsf {np} $の問題でも一般的に真であることは知られていません。

Answer 2

あなたの証明の簡単な反例：$ 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）$ so $ m'_2（f（x_2）、 langle 1、x_1、w rangle））= m_1（x_1、w）= 1 $ so $ 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 $の有効な証明書ではありません