あなたは四百人の大学生のグループのための住宅の宿泊施設を整理しているとします。 スペースは限られており、学生の唯一の百人が寮内の場所を受け取ることになります。 問題を複雑にするために、学部長は互換性のない学生のペアのリストをあなたに提供し、このリストからのペアがあなたの最終的な選択に現れない, これはコンピュータ科学者がNP問題と呼ぶものの例であり、同僚によって提案された百人の学生の与えられた選択が満足できるかどうかを確認するのは簡単である（すなわち、同僚のリストから取られたペアも学部長のオフィスからのリストに表示されない）が、そのようなリストをゼロから生成するタスクは完全に実用的ではないほど難しいようである。 確かに、四百人の応募者から百人の学生を選ぶ方法の総数は、既知の宇宙の原子の数よりも大きいです！, したがって、将来の文明は、100人の学生の可能なすべての組み合わせをチェックすることによって、ブルートフォースで問題を解決できるスーパーコンピュータ しかし、この困難の場合のみ反映されな工夫を凝らのプログラマを交換してください。 実際には、コンピュータサイエンスにおける顕著な問題の一つは、その答えはすぐにチェックすることができますが、任意の直接手順によって解決する, 上記のような問題は確かにこの種のものであるように見えますが、これまでのところ、誰もそれらのいずれかが実際に表示されるほど難しいこと、すなわちコンピュータの助けを借りて答えを生成する実現可能な方法がないことを証明することはできませんでした。 スティーブン-クックとレオニード-レヴィンは、1971年にp（すなわち、見つけやすい）対NP（すなわち、チェックしやすい）問題を独立に定式化した。
画像クレジット：左に、Jiří Janíčekによってスティーブン*クック（トリミング）。 CC BY-SA3.0