Sharp-Pとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Sharp-Pの意味・解説 

#P

(Sharp-P から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/08/17 10:04 UTC 版)

計算複雑性理論において、複雑性クラス #P とは、NP に属する決定問題に対応した数え上げ問題の集合である。多くの複雑性クラスとは異なり、決定問題のクラスではなく、函数問題のクラスである。

NP 問題は多くの場合「ある制約を満足する解は存在するか?」という形式である。例えば、次のようなものがある。

#P 問題は、これらの「存在するか」の部分を「いくつ存在するか」に置き換えたものである。例えば、次のようなものがある。

  • ある整数のリストから部分集合を選んで、合計がゼロになるような組合せはいくつ存在するか?
  • 与えられたグラフで、コスト 100 以下のハミルトン路はいくつ存在するか?
  • 与えられた連言標準形の論理式を満足する(真とする)変数の値の組合せはいくつ存在するか?

より形式的に言えば、#P は函数問題のクラスであり、「f(x)を計算せよ」という形式である。ここで f は、ある NP 機械の受容経路数を与える函数である。

明らかに、#P 問題は対応する NP 問題よりも難しい。解を数え上げるのが簡単なら、解があるかどうかを知るのはもっと簡単なはずである。従って、NP完全問題に対応した #P 問題は、NP困難となる。

驚くべきことに、一部の難しいといわれる #P 問題は、比較的易しい P 問題に対応したものである。

#P に最も近い決定問題は PP である。これは、計算経路の多数(半分以上)が受理されるかどうかを問うものである。つまりこれは #P 問題の答えの最上位ビットに対応している。決定問題クラス ⊕P は、逆に #P の答えの最下位ビットを答えとするものである。

戸田の定理の結論の1つとして、多項式時間機械に #P 神託機械を付与したもの(P#P)は PHに属する全問題(多項式階層全体)を解くことができる。実際、多項式時間機械は1回だけ #P の神託を受けるだけで PH に属する任意の問題に答えることができる。これは、#P完全な問題を解くことが非常に困難であることを如実に示している。

参考文献




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  
  •  Sharp-Pのページへのリンク

辞書ショートカット

すべての辞書の索引

「Sharp-P」の関連用語

Sharp-Pのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Sharp-Pのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの#P (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS