問題タブ [np]

スタンフォード大学の Tim Roughgarden 教授は、MOOCを教えているときに、クラス NP の問題の解は長さが多項式でなければならないと述べました。しかしウィキペディアの記事によると、NP 問題は決定問題です。では、クラス NP には基本的にどのような種類の問題があるのでしょうか? また、そのような問題の解には多項式の長さの出力があると言う必要はありません (決定問題は必ず 0 または 1 を出力するため) ?

2 倍の指数時間でしか解けないコンピュータ サイエンスの重要な問題はありますか? そして、それらが存在する場合、それらはどのクラスの問題に属しますか?

n 種類の長方形の 3-D ボックスのセットが与えられます。ここで、i^ 番目のボックスは高さ h(i)、幅 w(i)、深さ d(i) (すべて実数) です。できるだけ高さのあるボックスのスタックを作成したいのですが、ボックスを別のボックスの上にスタックできるのは、下のボックスの 2 次元ベースの寸法が 2 次元ベースの寸法より厳密に大きい場合だけです。ハイボックスのDベース。もちろん、ボックスを回転させて、任意の側面がベースとして機能するようにすることもできます。ボックスで複数のインスタンスを使用することはできません。

この質問は SO ( Box stacking problem ) で尋ねられましたが、「繰り返しなし」の制約はありません。LIS を使用してこれをどのように解決しますか。

私は次の解決策を考案しました。議論できますか

ここで、 h[j'] は、 j 番目のボックスが H[i] の計算に既に使用されている場合に他なりません。回転が許可されているため、H[j] は j 番目のボックスの幅または深さになります。

ここで説明されている問題を考えてみてください（以下に再現）。よりよく知られているNP完全問題をそれに還元することはできますか？

問題：

家の列があります。各家は、赤、青、緑の3色で塗装できます。それぞれの家を特定の色で塗る費用は異なります。隣接する2つの家が同じ色にならないように、すべての家をペイントする必要があります。あなたは最小の費用で家を塗らなければなりません。どうしますか？

注：ハウス1の赤の塗装のコストは、ハウス2の赤の塗装のコストとは異なります。家と色の組み合わせごとに独自のコストがあります。