難しいタスクと複雑なタスクには大きな違いがあります。 最悪の場合、タスクには効果的な解決策がない場合がありますが、ほとんどの場合、または実際に発生する場合は、簡単に解決できます。 したがって、一般に受け入れられているタスクの複雑さの定義は、2つのタスクがNP完全な場合もあるが、ほとんどの場合1つは迅速に解決でき、もう1つはそうではないため、実際の複雑さの点では比較的無意味であることがわかります その結果、「平均複雑度」の概念は、複雑度理論で重要な役割を果たします（ここで、「平均」は、解法時間の数学的期待値です）。
この概念の中心的な役割を説明するために、5つの異なる可能性のある世界を想像して（可能性があります-それらが非現実的であり、私たちの世界がそれらのいずれかであることが判明していないためです）
特に、人間の観点からデモンストレーションするために、クラスにタスクを依頼した数学の先生であるグレース教授の悲しい話を使用します。1から100までの数字の合計を数えます。算術的進行の規則性に気付き、この量をほぼ瞬時に計算しました。 しかし、この後、教授はガウスに復takeし、クラス全体の前で彼を屈辱し、ガウスが解決できない課題を発明するという強迫観念を持っていることを知っている人はほとんどいません。 これにより、教授はマッドハウス（特に19世紀の中で最も快適な目的ではない）に導かれ、ガウスは数論アルゴリズムに興味を持ちました。 私たちが検討するさまざまな世界で何が起こるか想像してみましょう。
アルゴリズム
アルゴリズムは、P = NPの世界です。 この世界では、教授は現実よりも恵まれていません。 教授は、ガウスに自分（教授）がクラスに正しい答えを提示しなければならないタスクで困惑する必要があるため、タスクの選択は、簡単に検証可能な解決策（つまり、NPからの問題）を持つものに限定されます。 Gaussは検証方法を使用して、この問題を自動的に解決できます。
正しい解を検証するアルゴリズムから問題を解決するアルゴリズムを自動的に取得する方法は、その世界のコンピューターサイエンスに革命をもたらします。 不適切と思われるタスクは簡単です。 ほぼすべての最適化タスクは簡単で自動化されます。 たとえば、ヒューリスティックはVLSI設計では使用されなくなり、最適性の基準が指定されている場合、最適な配線が生成されます。 プログラミング言語には、計算の実行方法を説明する指示が含まれなくなりました。 代わりに、入力に関連して出力に必要なプロパティのみを記述します。 コンパイラは、仕様言語を独立してソリューションアルゴリズムに変換します。
P = NPが人工知能の多くの側面を些細なものにすることはそれほど明白ではありません。 Occamカミソリの原理に基づいた学習システムを使用して、コンピューターを自動的にトレーニングして、人々が実行できるアクションを実行できます。 人間の専門家が作成した入力データと出力データのトレーニングサンプルを提供するだけで十分で、コンピューターは専門家と同じ答えを生成する簡単なアルゴリズムを出力します。 したがって、コンピューターに自然言語の文章を認識して解析するように教えることができます。正しい文章と間違った文章の十分な数の例を提供するだけで済みます（ここでは、自然言語の解析に使用する簡単なアルゴリズムがあると仮定しています）。
一方、アルゴリズムでは、情報の観点から人とコンピューターを区別することはできません。 言及された学習アルゴリズムは、他の機械や人の振る舞いをシミュレートするために簡単に学習できます。 開発可能なコードは、同様に簡単にクラッキングできます。 同じアルゴリズムは少数の暗号文とプレイテキストのペアで簡単に取得できるため、コードの基になっているアルゴリズムを非表示にする試みはほとんど役に立ちません。 このようにすべての人がアクセスできるようにすることなく、複数の人に情報へのアクセスを提供することはできません。 したがって、識別方法は物理的な測定に基づいている必要があります。 また、識別セキュリティは、物理パラメータの不変性と、メーターから識別デバイスへのデータ伝送チャネルの外部影響に対する耐性に基づいています。
発見的
ヒューリスティックは、NPからの問題が最悪の場合に効果的な解決策を持たない世界ですが、（複数の入力の確率分布について）平均して簡単に解決できます。
ヒューリスティックは、ある意味、逆説的な世界です。 NPからのタスクには複雑なインスタンスがありますが、そのような複雑なインスタンスを見つけること自体が難しいタスクです。 この世界では、教授はガウスにとっては難しすぎるタスクを見つけることができます。 しかし、彼はガウスが日中に解決できないタスクを検索するのに1週間費やし、ガウスが1か月に費やすタスクを見つけるのに1年を費やす必要があります（この場合、ガウスは最終的に教授よりも多項式の優位性があると仮定されます天才）。 おそらく、人生がラズベリーのように思えない限り、人生は私たちに複雑な仕事を提供するほど深刻ではありません。 したがって、実際の目的では、この世界はアルゴリズムとほとんど区別できません。
または、それはまだ区別可能ですか？ ヒューリスティックでは、NPから問題を解決する平均時間は、この問題を「考え直す」平均時間に依存します。 これは状況を多少複雑にします。 平均して、問題の解決策を計算することは、解決策を考案するよりも2倍長いと仮定します。 問題1の検討に時間Tを費やすと、解の計算に2T時間単位を費やします。 この問題の解決策は、問題2の解決策に影響します。 問題2の解決策を考えるために3T単位の時間を費やしました。 したがって、問題2の解決に6T単位の時間が費やされます。 これが問題番号3につながり、すでに10T単位の時間を費やしているため、20Tがソリューションに費やされます。 この再帰が指数関数的に増加するにつれて、ほんの数ステップで「実行可能」と「非現実」の境界を越えます。
VLSI設計の場合、仕様に適合するほとんどの可能なスキームにあまり関心がなく、仕様を満たす最小オプションが重要であるため、必ずしも効果的なソリューションはありません。 そのようなスキームは適切な分布を持たない可能性があり、それらを見つけるのに指数関数的な時間がかかる可能性が高いため、ヒューリスティックのアルゴリズムがうまく機能しない「最悪のケース」ではないという保証はありません。
暗号化とネットワークセキュリティでは、Algorithmicと基本的な違いはありません。 良心的なユーザーが一意に識別できるタスクのインスタンスを検索するのに多くの時間を費やし、攻撃者がこのインスタンスを同等の時間で解決できる場合、システムのクラッキングを望む攻撃者は、良心的なユーザー）。
ペシランディア
ペシランディアは最悪のケースです-平均的にも解決するのが難しいタスクがありますが、一方向の機能はありません。 一方向関数が存在しないということは、次のことを意味します：計算が簡単な問題については、xのほぼすべての値について、F（x）が与えられた場合、次のようなxを見つけることができるという意味で、逆問題の解を見つけることも簡単ですF（x '）= F（x）、さらに、F（x）の計算に費やされるのとほぼ同じ時間。
ペシランディアでは、教授は若い天才でさえ解決できないガウスの問題を尋ねることができました。 しかし、教授自身は解決策を示すことができなかったので、ガウスの屈辱は不完全でした。
この世界では、多くの分野でタスクに簡単な解決策はありません。 進歩は、私たちの世界と同じです。世界の理解を深め、完全に満足のいくヒューリスティックを使用することにより、ゆっくりと進歩します。 問題を解決する一般的な方法は、ほとんどの領域で機能しません。 ただし、一方向関数が存在しないことに基づいて、いくつかの有用なアルゴリズムが可能になります。 たとえば、入力データの分布を知っている場合、限界において、分布エントロピーに従ってそれらを予想される長さに圧縮することが可能なデータ圧縮方法。
この世界では、暗号化で複雑なタスクを使用することはできません。 誰も答えを知らないタスクを使用して、良心的なユーザーと攻撃者を区別することはできません。
ミニクリプト
minicryptには一方向の機能がありますが、公開鍵暗号化は不可能です。 ここで、厳密に言えば、公開鍵暗号化はこの問題を解決するための1つの方法にすぎませんが、公開鍵暗号化とは公共通信チャネルを介した秘密通信のタスクを意味します。
一方向関数を使用して、複雑だが解決された問題を生成できます。つまり、ジェネレーターはxを選択し、y = F（x）を計算し、検索タスクを「F（x '）= yのようなxを見つける」に設定します。 したがって、ミニクリプトでは、教授は最終的にクラス全体の前でガウスを倒すことができます。
ネットワーク上で、参加者は他のユーザーに対して自分自身を識別し、デジタル電子署名を使用してメッセージを認証できます。 秘密に含まれる他の秘密情報を明かすことなく、秘密に関する事実を証明することが可能になります。 参加者間で少量の情報が事前に送信される場合、2人のネットワーク参加者間に信頼できる秘密コードを設定できます。これにより、オープンな通信チャネルを使用して、密室で通信できます。 ただし、オープンチャネルを通じて秘密投票を実施したり、安全なチャネルを通じて事前に情報を送信せずに安全な交渉を確保したりすることはできません。 匿名のデジタルマネーを作成することはできません。
クリプトマニア
暗号マニアには、公開鍵暗号が存在します。 暗号マニアでは、ガウスはさらに辱されます。 教授と彼の好きな学生は、両方が答えを知っているタスクを共同で選択することができ、ガウスはそれを解決できません。 さらに、この世界では、教授はクラスの全員に、ガウスを除く特定の問題の解決方法を知らせることができます。
公開鍵プロトコルの存在は、一方向性関数の存在を意味します。したがって、この世界には擬似ランダム性、デジタル署名、識別、ゼロ知識プロトコルなどがまだ存在します。 また、一方向関数を使用して秘密の交換を秘密で実行する場合（およびすべての既知のプロトコルがこれらの関数を明示的または間接的に使用する場合）、考えられる暗号化タスクを解決できます。 プライバシーの作成が技術的な課題である他の世界とは異なり、クリプトマニアのテクノロジーは、反対に、プライバシーを減らすユーザーの能力を制限します。 市民にどれだけの機密性を許可するかについてのほとんどの決定は、技術的能力ではなく、政治的および社会的プロセスの結果として下されます。
この世界は私たちのものに最も似ています。少なくとも、有名な公開鍵プロトコルが信頼できると信じられている限り。
R.インパグリアッツォ、「 平均的なケースの複雑さの個人的見解 」、sct、pp。134、第10回複雑性理論会議（SCT'95）、1995年
XKCDウェブサイトから撮影した画像。