$ Max-SNP_0 $と$ Max-SNP $の違い

Max SNPは、Max SNP_0の問題に対してL-還元可能な問題の集合として定義されることが多くの場所で見られます(ex
[1]の場合)。

私は2つの質問があります:

1)私はMax SNPのオリジナルの定義([2]から)は最大SNP_0の定義だと思った!
(すなわち、論理の点では直接であり、縮小の必要性なしに)。 [1]と[2]の定義は同じですか?

2)私が知っているL減少の唯一の用途は、問題が最大SNPであることを示すことであり、与えられた問題がMax
SNPにあることを示すことではありません。このようにL削減が使われる例はありますか?

前もって感謝します!


リファレンス


[1] Mikhail J. Atallah、Marina Blanton。計算ハンドブックのアルゴリズムと理論

[2] C.H.PapadimitriouおよびM.Yannakakis。最適化、近似、および複雑さのクラス

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です