NP ハードはハードという意味ではありません ||数学∩プログラミング

NP 困難性がインターネット上に現れると、たとえば、愚かなブロガーがビデオ ゲームについて書きたいなどの理由で、NP 困難であることが証明されている問題は実際には非常に難しいと結論付けたくなることがよくあります。

「スーパーマリオはNPが難しいと科学者が証明した？私は自分がマリオを苦手とするのには理由があるとずっと思っていたんだ！」ごめんなさい、この二つは関係ありません。 NP 硬度とは、狭い意味での硬いことを意味します。この投稿で明確になることを願っています。その後、NP 硬度を超えてプログラマーとしての仕事に応用できる、数学的な意味での「ハード」の意味を探っていきます。

問題が NP 困難である場合、それは単純に、その問題を使用してロジックを表現できるほど、問題が十分に表現力豊かであることを意味します。これは、AND、OR、NOT を使用したブール式を意味します。スーパー マリオの例では、「問題」は、(1) プレーヤーのコントロール、(2) レベルを構成する許可されたタイルとキャラクター、(3) 最初から最後まで到達するという目標の束です。論理式はレベルの作成時にエンコードされ、問題を解決する (レベルを完了する) ことは、論理式が成り立つ条件を見つけることと同じです。

この意味では、宝具の硬さがスーパーマリオのすべてを硬くするわけではありません。論理式をエンコードするために設計されたレベルは、不自然で、複雑で、歪んでいます。彼らはゲームのルールを悪用して、ゲームにブール論理を詰め込みます。これらは 最悪の場合のレベル。これはマリオをまったく意図しない目的に使用するものであり、ハッキングと何ら変わりません。したがって、NP 硬度は最悪の場合の主張です。

繰り返しになりますが、NPの硬さはスーパーマリオが持っていることを意味します。 表現力。表現力が非常に高いため、最悪の場合には難しいと思われる他の問題もエミュレートできます。そして、数学的な「難易度」の目標はアルゴリズムの限界について推論することであるため、スーパー マリオを完全に一般的に解くことができるということは、レベル デザインがどれほどばかばかしいものであっても、どんな難しい部分問題も解決できることを意味します。

P != NP 予想は、ブール論理式が充足可能かどうかを決定する多項式時間アルゴリズムが存在しないことを示しており、その結果、スーパー マリオには (完全に一般的に) 多項式時間アルゴリズムも存在しません。

そうは言っても、実際には、スーパー マリオのレベルは論理式をエンコードしていません。現実世界のスーパー マリオのレベルはそのように (解けるように、楽しく) 設計されているという知識を使えば、アルゴリズムを使ってスーパー マリオを解くことができます。多くの例があります。

一般に、人間にとっての問題の難しさは、アルゴリズムの難しさとは無関係です。整数の乗算を考えてみましょう。これはコンピュータにとって解決できる些細な問題ですが、人間はこの問題に苦戦する傾向があります。コンピューターが 2,000 桁の数値を数ミリ秒で掛け算できるのに対し、7 桁の数値 2 つを 5 秒以内に掛け算できるのは驚くべき偉業です。

一方、タンパク質の折り畳みは NP が困難な問題として知られていますが、人間にとって十分に簡単に解決できるゲームに変換されており、プレイヤーは科学研究に貢献しています。実際、巡回セールスマンなど、最も一般的に引用される NP 困難な問題の一部でさえ、地球上のすべての都市と同じくらいの規模の入力で数時間以内に (最適に非常に近い) 問題を解決できるヒューリスティックで実用的なアルゴリズム ソリューションを備えています。

したがって、硬度の数学的概念は、実際の硬度の概念からまったく切り離されています。これは、一部の NP 困難問題を任意の精度内で効率的に近似できることは言うまでもありません。

数学をもう少し掘り下げてみましょう。 「ハードネス」は、アルゴリズムによる解決策の再利用性に基づいた問題間の比較に関する一連のアイデアです。大まかに言うと、$ R$ を解くアルゴリズムが $ C$ の任意の問題を解くアルゴリズムに簡単に変換できる場合、問題 $ R$ は問題のクラス $ C$ に関して困難です。どのような種類の変換が許可されるかを指定する必要があり、その変換は $ C$ のターゲット問題ごとに異なる可能性がありますが、それが基本的な考え方です。

スーパー マリオの例では、論理式を解きたい場合、式をレベルとしてエンコードし、その上でマリオ レベル プレイ アルゴリズムをブラック ボックスとして実行することにより、仮定上完璧なマリオ レベル プレイ アルゴリズムを論理ソルバーに変換できます。最後に if ステートメントを追加して、「レベルを完了できる/できない」を「式を満たせる/満たせない」に変換すると、変換は完了です。 NP 硬度にとって、変換にかかる時間は多項式のみであることが重要です。他の種類の硬度では、より多くのリソースを許可したり、より少ないリソースに制限したりする可能性があります。

ブール論理の充足性は NP 困難であるため、これがマリオを NP 困難にしている理由です。 NP におけるあらゆる問題はブール論理ソルバーによって解決でき、したがってマリオレベルのプレイヤーによっても解決できます。ブール論理の解決が NP 困難であるという事実は、証明するのが難しい定理です。しかし、それが真実であると仮定すると、NP 問題からスーパー マリオへの変換を構成することができます。

異なる種類の難易度の簡単な例として、有限量のメモリ (入力とは無関係) のみを使用して解決できる問題のクラスを $ C$ とすることができます。おそらく、このクラスの問題については別の名前で聞いたことがあると思いますが、投稿が終わるまで推測したままにしておきます。 $ C$ 困難な問題 $ R$ は、有限メモリで解決可能な問題を解決するためにアルゴリズムによる解決策を再利用できる問題です。

注意が必要です。NP 硬度の場合のように、解間の変換で (入力のサイズで) 多項式時間が許容される場合、変換だけで問題全体を解決するのに十分な時間があり、そもそも $ R$ の解を求める必要がなくなります。このため、変換で実行できる作業量を制限する必要があります。ここで、硬度の定義がどれだけ興味深いか、あるいは役立つかに影響を与える選択肢が得られますが、1 つだけ選んで、変換では有限の値のみを使用できるとしましょう。 時間 (入力とは独立しています)。

公平を期すために言うと、この定義に関して難しい問題があるかどうかは実際のところわかりません。おそらく存在しますが、彼らが $ C$ のメンバーではない可能性が高く、硬度の定義が非常に興味深いのはそこです。 $ C$ に問題があり、これも $ C$ 難しい場合は、次のように呼ばれます。 完了 $C$で。そして、完全な問題を発見したら、理論的な観点から言えば、あなたは勝者です。 $ C$ の問題解決の難しさを典型的に示す問題が見つかりました。したがって、複雑さのクラスを研究する研究者にとって、完全な問題を見つけることが中心的な目的となります。ビジネス業界でよく言われるように、「ABC: 常に完了すること」です。

より具体的で興味深い例として、すべての多項式時間で解ける問題のクラス $ P$ には完全な問題があります。ここでの変換は少し宙に浮いた状態です。それらは、対数空間計算、または多対数時間 (非常に高速な) 並列計算と考えることができる NC と呼ばれるもののいずれかです。 NC についてのみ言及したのは、NC を使用すると「P 完全問題は並列化するのが難しい」と言えるからです。

どちらを選択しても、P 完全として知られる非常に便利な問題が多数あります。 1つ目は、 回路値の問題、回路 (合理的なエンコーディングを使用してゲートと配線によって記述される) と回路への入力が与えられた場合、出力は何でしょうか?

その他には、線形計画法 (線形制約に関してこの線形関数を最適化する)、データ圧縮 (Lempel-Ziv-Welch を使用した文字列 $ s$ の圧縮バージョンには文字列 $ t$ が含まれますか?)、部分型の型推論などがあります。 Greenlaw らのこの要約には、さらに多くの内容が記載されています。それぞれは、他のインスタンスの任意のインスタンス、および P の問題の任意のインスタンスをエンコードするのに十分な表現力を持っています。 gzip が線形プログラムを解決できると考えるのは非常に興味深いですが、それは、スーパー マリオ レベルでブール論理をエンコードすることよりも不思議ではありません。

NP 難易度の場合と同様に、問題が P 難易度であっても、それが人間にとって簡単か難しいか、または典型的なインスタンスが簡単に並列化できないことを自動的に意味するわけではありません。 P 硬度も最悪の場合の保証です。

P 完全性を研究することは、NP 完全性が役立つのと同じように役立ちます。完全性は、完璧な解決策を見つけることを望むべきか、それとも近似やヒューリスティックに満足すべきか (または、問題のコンテキストを組み込んで簡単にするか) を示します。問題が P-complete であることがわかっているということは、期待すべきではないことを意味します 完璧 効率的な並列アルゴリズム、または 完璧 非常に限られたスペースを使用する効率的なアルゴリズム。問題が NP 困難であるとわかっているということは、問題を期待すべきではないことを意味します。 完璧 多項式時間解。言い換えれば、これらの制限を課せられた場合、ゲームはトレードオフの 1 つになります。厳格さと完全性により、作業が集中して迅速化され、原則に基づいた意思決定プロセスが明確になります。

次回まで！

PS 有限のメモリ量で解決できる問題のクラスは、まさに通常の言語のクラスです。 「有限メモリ」は、それらを解決するために使用される有限状態マシンです。

---

---