algorithm - 多項式時間を使用する「最も難しい」問題は何ですか?

Question

最近、私は次のようなセミナー作品を読みました。

[一般的なグラフの] マッチングアルゴリズムは、重み付きの場合に拡張できます。これは、多項式時間で解くことができる「最も難しい」組み合わせ最適化問題の 1 つと思われます。

すぐに次の疑問が頭に浮かびました。

他の「P-hard」問題を知っていますか?

今のところ、P-hard を次のように定義したいと思います。(または、多項式時間で問題を解決する決定論的アルゴリズムが既にある場合、どのように「ハード」をより適切に定義できますか?)

score 10 · Accepted Answer

10

于 2010-02-13T20:43:37.937 に答える

score 6 · Accepted Answer

実際には「P完全」問題があります。つまり、多項式時間で計算できる他のすべての問題をそれらに縮小できます。http://en.wikipedia.org/wiki/P-completeを参照してください。

score 5 · Accepted Answer

別の「難しい」P 問題は、「線形計画法」を解くことです。

score 3 · Accepted Answer

ルールを少し曲げたい場合、疑似多項式時間アルゴリズムは、「多項式時間」で解決できる「最も難しい」アルゴリズムです。

疑似多項式アルゴリズムの典型的な例は、ナップザック問題O(nW)に対する動的計画法ソリューションです。

score 2 · Accepted Answer

5 に答える 5