他の種類の削減の下でPとNPに完全な問題はありますか？

cs.stackexchange https://cs.stackexchange.com/questions/2222

  •  16-10-2019
  •  | 
  •  

質問

複雑なクラス$ mathsf {p} $には、完全な問題があることを知っていますwrt $ mathsf {nc} $および$ mathsf {l} $削減。

これらの2つのクラスは、$ mathsf {p} $が完全な問題を抱えている削減の唯一のクラスですか？

また、多項式時間削減の横にある$ mathsf {np} $に使用できるクラスの削減は何ですか？

役に立ちましたか？

解決

あなたの質問には、いくつかの誤ったまたは不明確なフレーズが含まれています。 「Complexity Class XにはYが削減されている」も、「複雑さのクラスXにY削減を使用できます」も理にかなっていません。さらに、「多項式時間削減」という名前で知られている少なくとも2つの定義があります。どちらもNPの完全性を研究するために使用されます。しかし、この答えでは、多くの1つの削減とチューリング削減の違いを無視し、削減のリソース制限のみに焦点を当てます。

今、私はあなたが尋ねたいことを言い換えて、彼らに答えます。

多項式時間削減以外に、NP不完全性を定義できる削減の定義はありますか？ NCの削減とログスペースの削減以外に、どのPコンプレテス性を定義できるかに関する削減の定義はありますか？

ArtemとRaphaelが言ったように、あなたはあなたが好きなものを定義することができます。

多項式時間削減を除き、文献のNPの完全性を研究するために実際に使用される削減の定義はありますか？ NCの削減とログ空間削減以外の文献のPコンフィリンネスを研究するために実際に使用される削減の定義はありますか？

はい。たとえば、Papadimitriouは、NPの完全性の定義を含む、教科書[PAP94]全体でログスペースの削減を使用しています。 （注：[PAP94]では、「L-Reduction」という用語は、ログ空間削減とはまったく異なるものを意味します。）P-Completenessに関しては、NCk GHMRSS00]で削減が言及されています。これはNC削減の特別なケースであり、ログスペースの削減よりも一般的です k≥2.

しかし、それらは本当に異なる概念ですか、それとも同じ概念の単なる異なる定義ですか？

現在、誰も知りません。たとえば、l = pの場合にのみ、ログスペースの削減と多項式時間削減が同等です。

GHMRSS00] Raymond Greenlaw、H。JamesHoover、Satoru Miyano、Walter L. Ruzzo、Shuji Shiraishi、およびTakayoshi Shoudai。 並列計算プロジェクト：ボリュームI〜III, 2000. http://www.cs.armstrong.edu/greenlaw/research/paralleal/

PAP94] Christos H. Papadimitriou。 計算の複雑さ. 。 Addison-Wesley、1994年。

他のヒント

複雑なクラス$ c $が$ a $のクラスの下で完全な問題を抱えている場合、$ c $の下および$ a $を含む削減のクラスで同じ問題が完了することに注意してください。

通常、完全性の証明は、通常述べられているよりもはるかに弱いクラスの削減で通過します（例：$ mathsf {ac^0} $削減）。 $ mathsf {ac^0} $を含む削減のクラスで十分であり、そのようなクラスの数は多くありません。

また、次の論文を確認することもできます。

  • Agrawal、M、Allender、E.、Impagliazzo、R.、Pitassi、T。、およびRudich、S。」減少の複雑さを減らす"、Journal of Computational Computionity、10、pp.117-138、2001。

アルテムが彼に指摘しているように コメント, 、あなたが好きなものを定義できるので、質問はかなり気が狂っています。物事が「ちょっと愚かな」ものになり始める場所を説明させてください。

いくつかの表記法：2つの問題について$ p、q $、$ p leq_f q $ for of functions $ f $の場合は、$ f in f $が$ p（x）= q（f（x）がある場合）$すべての入力$ x $（$ p $）、つまり$ p $が$ f $を$ q $に還元できる場合。 $ x $ completeの問題のクラスに対して$ xc_f $を$ f $、つまり

$ qquad displaystyle xc_f = {p in x mid forall q in x. q leq_f p } $。

さらに、$ T_X $で、一部のセット$ x $で関数を計算するアルゴリズムの（漸近的に最適な）ランタイム関数のセットを示します。

ここで、問題の任意の（複雑さ）クラス$ x $¹を検討してください。削減スペースを時間の複雑さの観点から制限する場合 - ここではすべてが可能です - およそ2つのケースがあります。

  • $ t_f supseteq omega（t_x）$²-削減は問題解決者よりも速くありません。

    この場合、$ xc_f = x $ - これは、複雑さ理論にとって明らかにそれほど興味深いものではありません。このような$ f $を考慮すると、特に$ t_f subseteq theta（x）$の場合、実際には役立つかもしれません。 $ x $のすべての問題を、非常にうまく解決できるいくつかの問題に減らすことができます。線形プログラミングとSATは、高度に最適化されたLP-RESPのために典型的な例です。 SATソルバー。

  • $ T_F SubseteQ O（X）$ - 削減は問題解決策よりも速いです

    ここで興味深いことが起こる可能性があります。つまり、$ xc_f subset x $または$ xc_f neq xc_ {f '} $です。これらの事実に興味深い影響があるかどうかは、$ x $と$ f $の具体的な選択に依存します。 $ xc_f = emptyset $が発生する可能性があることに注意してください。それ自体が十分に興味深いことです。

    $ f $を選択すると、物事は間違いなく面白くなくなります。 $ x = mathsf {np} $および$ f $を考えてみてください。削減は入力サイズを大幅に縮小する必要があり、それにあまりにも多くの時間を費やすことはできないため、$ f $はそれほど強力ではありません。

    ただし、$ T_F Subseteq O（1）$への制限でさえ、意味のある関係を残すことに注意してください。たとえば、「$ x $は均一な整数ですか？」 「$ x $の最初のビット0？」に削減できます。 $ o（1）$の時間とスペース。したがって、そのような弱い削減でさえ、どの問題が他の問題が削減の複雑さの観点から近くにあるかを調べることは興味深いかもしれません。クラシック$ mathsf {npc} = mathsf {np} c_p $削減にそのような違いがあります。

技術的には、3番目のケースがあります。たとえば、$ t_f = p $ and $ t_x = theta（n^3）$;この場合、$ f $が合理的に豊富な場合 - ケース1のコメントが適用されます。また、$ f $が該当するケースの質問自体が興味深いかもしれないということに注意してください：「$ mathsf {p = np} $？」基本的に、$ t_f = theta（x）$かどうか（および$ f = theta（xc_f）$かどうか）。

  1. 「適切な」複雑さのクラスになるためには、何らかの「下向きの閉鎖」のWRTの複雑さである必要があります。
  2. $ circ（x）$ for a function class $ x $および$ circ $ acrauシンボルは、通常のlandauシンボルの自然な拡張です。 （f）$。
ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top