5

無限の数の処理ユニットと無限のスペースが与えられた場合、合理的な時間内に O(n!) の複雑さの問題を解決することは可能ですか?

O(n!) 問題の典型的な例は、すべての順列 (順序付けられた組み合わせ) を試すブルート フォース検索です。

4

10 に答える 10

6

確かにそうです。巡回セールスマン問題を厳密な NP 形式で考えてみましょう。各地点から各地点への移動にかかる費用のリストが与えられた場合、費用が K よりも少ないツアーをまとめることができますか? Intel の新しい無限コア CPU を使用すると、可能な順列ごとに 1 つのコアを割り当て、コストを合計し (これは高速です)、いずれかのコアが成功のフラグを立てるかどうかを確認するだけです。

より一般的に言えば、NP の問題は、潜在的な解を多項式時間で (つまり、効率的に) 検証できるような決定問題であり、(潜在的な解は列挙可能であるため) 十分な数の CPU で効率的に解くことができます。

于 2010-03-29T16:52:46.720 に答える
6

あなたが本当に求めているのは、非決定論的なマシンで O(n!) の複雑さの問題を O(n^a) に減らすことができるかどうかということです。つまり、Not-P = NP かどうか。その質問に対する答えはノーです。NP ではない Not-P 問題がいくつかあります。たとえば、制限付き停止問題 (プログラムが最大 n! ステップで停止するかどうかを尋ねる)。

于 2010-03-29T16:56:37.103 に答える
2

問題は、作業の分散と結果の収集です。

すべての CPU が一度に同じメモリを読み取ることができ、それぞれが既知の固有の CPU-ID を持っている場合、ID を使用して順列を選択することができ、分散の問題は一定時間で解決できます。 .

ただし、結果を収集するのは難しいでしょう。各 CPU はその (数値) 隣人と比較し、その結果を 2 つの最も近い隣人の結果と比較するなどです。これは O(log(n!)) プロセスになります。よくわかりませんが、 O(log(n!)) は超多項式であると思われるので、それが解決策だとは思いません。

于 2010-03-29T16:59:20.123 に答える
1

これは、ワードプロセッサを搭載したサル破壊防止コンピュータで入力するサルの数が無限であるかどうかを尋ねるようなもので、シェイクスピアのすべての作品を思い付くことができます。与えられた時間は無限です。条件が物理的に不可能であるため、現実主義者はそうは言わないでしょう。理想主義者はそう言うでしょう。理論的にはそれが起こる可能性があります。ソフトウェアエンジニアリング（コンピュータサイエンスではなくソフトウェアエンジニアリング）は、私たちが見たり触れたりできる実際のシステムに焦点を当てているため、答えはノーです。あなたが私を疑っているなら、それを作って、私が間違っていることを証明してください！私見では。

于 2010-03-29T18:03:15.553 に答える
1

場合によっては、「コードベースでこれを何回思いつくか?」というのが正しい答えです。しかし、この場合、本当の答えがあります。

すべての問題を完全な並列処理で解決できるわけではないため、正解はノーです。たとえば、巡回セールスマンのような問題は、旅の 2 番目の行程を検討するために 1 つのパスにコミットする必要があります。

都市の完全に接続されたマトリックスを想定すると、疲れたセールスマンのためにすべての可能な非循環ルートを表示したい場合、O(n)*O( (n-1)!) 問題。問題は、残りのパス (方程式の O((n-1)!) 側) を考慮する前に、1 つのパス (方程式の O(n) 側) にコミットする必要があることです。

一部の計算は他の計算の前に実行する必要があるため、単一のスキャッター/ギャザー パスで結果を完全に分散する方法はありません。つまり、ソリューションは、「次の」ステップを開始する前に計算の結果を待つ必要があります。これが重要です。以前の部分的なソリューションの必要性は、計算を進める能力に「ボトルネック」をもたらすからです。

これらの無限に高速で無限に多数の CPU を待機させることができることを証明したので (それらが自分自身で待機している場合でも)、ランタイムが O(1) になることはあり得ないことがわかっています。 「許容できない」実行時間を保証する大きな N。

于 2010-03-29T19:21:07.313 に答える
1

検索は「典型的な」問題だとおっしゃいましたが、実際には検索の問題について具体的に質問されましたか? もしそうなら、はい、検索は通常並列化可能ですが、私が知る限り、O(n!) は原則として利用可能な同時実行性の程度を意味しませんよね? 完全にシリアルな O(n!) 問題が発生する可能性があります。これは、無限のコンピューターが役に立たないことを意味します。私はかつて、実際には完全に連続した異常な O(n^4) 問題を抱えていました。

したがって、利用可能な同時実行性が最初のことであり、私見では、インタビューでアムダールの法則を持ち出すことでポイントを獲得する必要があります。次の潜在的な落とし穴は、プロセッサ間通信であり、一般的にはアルゴリズムの性質です。たとえば、次のアプリケーション クラスのリストを考えてみましょう: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine。FWIW 前述の O(n^4) コードは、FSM カテゴリに分類されます。

もう 1 つのやや関連する逸話: スーパーコンピューター ベンダーのエンジニアが、CPU 時間の 10% が MPI ライブラリに費やされていれば、並列化は確実に成功したと考えていると主張しているのを聞いたことがあります (計算化学ドメイン）。

于 2010-03-29T17:53:46.243 に答える
1

問題が、複雑さ O(n!) の問題に対する順列/回答のチェックの 1 つである場合、もちろん、無数のプロセッサを使用して効率的に実行できます。

その理由は、問題のアトミック ピース (問題のアトミック ピースは、たとえば、チェックする順列の 1 つかもしれません) を対数効率で簡単に分散できるからです。

簡単な例として、プロセッサをいわば「バイナリ ツリー」として設定できます。ルートにいて、プロセッサに問題の順列 (または問題の最小の部分が何であれ) をリーフ プロセッサに渡して解決させることができ、log(n!) で問題を解決することになります。時間。

長い時間がかかるのは、プロセッサへの順列の配信であることを忘れないでください。問題自体の各部分は、実際には即座に解決されます。

編集：以下のコメントに従って私の投稿を修正しました。

于 2010-03-29T17:01:11.167 に答える
1

いいえ、ん！NPよりもさらに高い。無制限の並列処理を考えれば、NP 問題を多項式時間で解くことができます。これは通常、「妥当な」時間の複雑さ N と見なされます。問題は、そのような設定ではまだ多項式よりも高くなります。

于 2010-03-29T17:28:20.063 に答える
0

セットアップのコストを無視して（たとえば、処理ユニットに値の範囲を割り当てるなど）、そうです。このような場合、無限大未満の値は、同じ数の処理ユニットにわたる1回の同時反復で解決できます。

ただし、セットアップは無視することが重要です。

于 2010-03-29T16:47:16.913 に答える
0

それぞれの問題は1つのCPUで解決できますが、これらのジョブをすべての無限のCPUに提供するのは誰でしょうか。一般に、このタスクは一元化されているため、すべての無限のCPUに配信する無限のジョブがある場合、それを行うのに無限の時間がかかる可能性があります。

于 2010-03-29T17:03:07.073 に答える