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

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


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

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

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

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

オリジナルのスーパー マリオ ブラザーズの句ガジェット。3 つの変数の OR をエンコードします。

この意味では、宝具の硬さがスーパーマリオのすべてを硬くするわけではありません。論理式をエンコードするために設計されたレベルは、不自然で、複雑で、歪んでいます。彼らはゲームのルールを悪用して、ゲームにブール論理を詰め込みます。これらは 最悪の場合のレベル。これはマリオをまったく意図しない目的に使用するものであり、ハッキングと何ら変わりません。したがって、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 有限のメモリ量で解決できる問題のクラスは、まさに通常の言語のクラスです。 「有限メモリ」は、それらを解決するために使用される有限状態マシンです。





Source link

Postagens Similares

  • Regresja i kombinacje liniowe || Matematyka ∩ Programowanie

    Ostatnio pomagałem w kursie algebry liniowej organizowanym przez Tai-Danae Bradleya i Jacka Hidary’ego i jedno z pytań, które pojawiło się kilka razy, brzmiało: „Dlaczego programiści powinni przejmować się koncepcją kombinacji liniowej?” Dla tych, którzy nie wiedzą, dane wektory $ v_1, \dots, v_n$, a kombinacja liniowa wektorów to wybór niektórych współczynników $ a_i$, za pomocą których…

  • جائزہ: عجیب و غریب – ایک نظریہ (الیگزینڈرا پلاکیاس)

    عجیب و غریب: ایک نظریہ بذریعہ الیگزینڈرا پلاکیاس جب ہم عجیب و غریب کے بارے میں بات کرتے ہیں تو ہم جس چیز کے بارے میں بات کرتے ہیں کھول دیتے ہیں۔ پلاکیاس نے اس بات کی کھوج کی ہے کہ کس طرح عجیب و غریب پن شرمندگی ، شرم ، بے چین اور اضطراب…

  • 飛行機への恐怖 – Kev Quirk

    2026 年 5 月 1 日 私は最近ネイサン・ミルワード著『ロング・ライド・ホーム』を読んでいたのですが、その本の中で彼は飛行機に乗らなければならないことと飛行機への恐怖について次のように語っています。 これは私が避けたかったこと(飛行機に乗るということ)であり、私の飛行機への恐怖は、上空での制御の欠如から生じたものである(と私は思います)。 すべては他人の手に委ねられています。何も悪いことが起こらないことを祈りながら、ただそこに座っていてください。なぜなら、もしそうなったとしても、人生でやるべきこと、やるべきことのすべてを考えている自由落下の瞬間より悪いことは考えられません。物事を正したり、間違いから学ぶにはもう手遅れだからです。あなたの時代がやって来ました、そして今はもう終わりです。これは飛ぶことと同じくらい、後悔することへの恐怖なのだと思いますが。 — ネイサン・ミルワード これ 本当に 仕事で半定期的に飛行機に乗る人にとって、飛行機が怖いと話すと、人々はよく驚かれます。 分からない、多分 恐れ 強すぎる言葉ですが、確かにとても不快な気持ちになります。特に乱気流がある場合。 ネイサンと同じように、それはコントロールの喪失だと思います。はい、そうです、私はバイクに乗っているときや自動車事故で怪我をする可能性がはるかに高いです。しかし、違うのは、車や自転車で事故に遭ったとしても、私はある程度コントロールできており、(特に車の場合)軽い怪我だけで済んでしまう可能性がかなりあるということです。 一方、飛行機事故に遭った場合、私は とても 可能な限り最も恐ろしい方法で死ぬ可能性が高く、それは私を完全に恐怖させます。私の旅行の多くが大西洋を横断するため、広大な水域を越えることが、この状況をさらに悪化させることがよくあります。素晴らしい。 それを克服するには? 神は私が試したことを知っています!私はブリティッシュ・エアウェイズで自信を持って飛ぶコースを受講したことがあり、知識は増えましたが、不安はあまり解消されませんでした。 睡眠薬を試したこともありますが、イギリスで市販されているものはどれもクソで、私にはまったく効果がありません。眠くなることもありません。何人かの人が鎮静剤を勧めましたが、それは私には不快です。それは違法であるだけでなく、彼らが私に何をするのかわかりません。結構です。 私は不安を抱えた飛行家になる運命にあると思うので、ただそれに対処しなければなりません。 数週間後にまたアメリカに行く予定ですが、いつものように不安が私の腹の中で湧き上がり始めています。 ヒントをお持ちの方がいらっしゃいましたら、ぜひお聞かせください。 意見 メールで返信 もっと購読してください! 私の最新のワッフルを読むために何度もここに来る必要はありません。新しいコンテンツを公開するたびに更新情報を受信できるように購読する方法が 2 つあります。 Source link

Deixe um comentário

O seu endereço de email não será publicado. Campos obrigatórios marcados com *