21

私は大学でアルゴリズム分析と呼ばれるコースを持っており、現在、さまざまな複雑さのクラス (P、NP、NP 困難など) を研究しています。

NP と NP 困難の交差点としての NP 完全問題、および NP に含まれる P 問題については既に説明しました。主に NP 完全問題 (k-coloring、k-clique、SAT) のいくつかの例についても説明しました。

ほとんどの場合、問題が NP 完全であることは次の方法で証明されます。

を。それを解決するための非決定論的アルゴリズムを見つける (選択、成功、失敗を使用する)。

b. 既知の NP 完全問題をそれに還元します。

問題は、これらの問題が決定論的マシンで実行された場合 (選択肢に遭遇したときに同時に分岐するのではなく、順次)、指数時間の解決策があることです。

私の質問はこれです-多項式時間でも指数時間でも解決できない問題に遭遇したことはありません。多項式時間の問題は通常 P であり、指数時間の問題は通常 NP 完全です。

ここに役立つベン図があります: http://en.wikipedia.org/wiki/Np_complete

  1. P でも NP-complete でも NP でもない問題の例を知りたいです。

  2. また、セットの累乗セットを NP 完全に生成するような、本質的に指数関数的な問題はありますか? それとも、その名前は、それを解決するための明白な方法が他にないという理由だけで、指数時間アルゴリズムが使用される問題にのみ適用されますか?

わかりました。Rosh Oxymoronに答えを与えました。なぜなら、彼は実際に、P と NPC の間にあると疑われる問題の例をいくつか挙げていたからです。皆さんの助けに感謝します。実際、この質問を間違った場所に置いていることに気付きました。もあります： https://cstheory.stackexchange.com/

ここで、私の質問に対する次の非常に役立つ回答を見つけ ました : 最初の質問に正確に関連していない場合でも、これは一般的に興味深いものです。

どうもありがとう、

ダン

4

4 に答える 4

13

PにもNP完全にもNPにもない問題の例を知りたいです。

私も; 100 万ドルの賞金を請求​​するには、次の Web ページにアクセスしてください: https://www.claymath.org/millennium-problems/p-vs-np-problem

于 2010-12-13T14:31:31.507 に答える
8
  1. 整数因数分解や離散対数 (クラッキング RSA と DSA) などの BQP 問題は、P の外側にあると考えられ、NP にあると疑われていますが、NP 完全にはないと考えられています。整数因数分解は NP にあることが知られており、P および NP 完全の外側にあると想定されています。

http://en.wikipedia.org/wiki/BQP

http://en.wikipedia.org/wiki/Integer_factorization

  1. NP は EXPTIME のサブセットですが、NP != EXPTIME であることが期待されます (つまり、EXPTIME 完全問題は NP にはありません)。P = NP と同様に、これはまだ証明されていません (ただし、P != EXPTIME であることが知られています)。たとえば、k ステップの後にアルゴリズムが半分になるかどうかのチェックは、EXPTIME-complete です。パワーセットを見つけることも（明らかに）です。

http://en.wikipedia.org/wiki/EXPTIME

于 2010-12-13T14:23:51.740 に答える
3

  1. にあることが知られている問題はありませんNP \ NPC。

  2. 問題は、非決定論的チューリング マシンが多項式時間で解決できる場合 (または、決定論的チューリング マシンが多項式時間で決定できる場合) に限り、NP になります。これはあなたの例には当てはまりません。

    さらに、 のすべての問題が多項式時間で解決できるP = NP可能性は完全にあり得ます (非常にありそうもないことですが) 。NPしたがって、ある問題が多項式時間で解けないことがわかっている場合、その問題は NP に含まれていないか、実際に NP に含まれていることを証明できる場合は、NP != P.

于 2010-12-13T14:36:09.713 に答える
1

Qiaochu Yuan、問題が NP 完全でないことを示すためにどのような手法が存在しますか?

役立つかもしれません。

于 2010-12-13T14:16:50.213 に答える