体系ガイド · 基礎から応用へ

計算可能性・還元・PとNP

「解けるか」と「効率よく解けるか」を分け、検証・還元・NP完全性の向きを整理する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 停止して答えることと速いこと
  2. PとNPは決定問題のクラス
  3. 還元は難しさを移す向きに注意
  4. NP完全性と実際の入力
  5. この記事をロゲイアに質問する理解を確かめる

停止して答えることと速いこと

決定問題は、入力に対してはい・いいえで答える問題です。決定可能とは、全ての正当な入力で停止して正しく答える手続きがあることです。実用的な時間で終わるという条件は、これだけでは含みません。たとえば候補を全て列挙する手続きが停止すると分かっていても、入力長に対して候補数が指数的に増えれば現実の計算は難しくなります。逆に停止性問題のように一般の入力全てを決定する手続きがない問題もあり、遅いアルゴリズムを速くする話とは区別します。

PとNPは決定問題のクラス

Pは入力長に関する多項式時間で決定できる問題のクラスです。NPは、答えが「はい」になる入力に対して多項式長の証拠があり、その証拠を多項式時間で検証できる問題のクラスとして説明できます。SATなら、候補となる真偽値割当てを受け取り、式を満たすかを調べる検証は速くできます。しかし割当てを見つけることまで自動で速くなるわけではありません。NPは「多項式時間では解けない」という略語ではなく、Pに属する問題もNPに含まれます。

還元は難しさを移す向きに注意

AからBへの多項式時間還元は、Aの入力をBの入力へ効率よく変換し、答えの対応を保つ方法です。Bを速く解ければ、この変換を使ってAも速く解けます。したがってBの難しさを示したいときは、既知の難しいAからBへ還元します。Bから簡単な問題へ還元できることを示すのとは向きが異なります。変換自体が指数時間かかるなら、多項式時間の議論には使えません。入力の大きさと、はい・いいえの両方向の対応も確認します。

NP完全性と実際の入力

NP完全な問題はNPに属し、NPの全ての問題から多項式時間で還元できます。PとNPが等しいかは未解決なので、NP完全であることだけから絶対に速い方法がないと断言してはいけません。また最悪計算量の主張は、全ての実例が同じように難しいことも意味しません。入力の構造、パラメータ、近似、ヒューリスティックで実用的に扱える場合があります。その際は厳密解か近似解か、どの入力条件で動くか、時間制限時に何を返すかを明記します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 22

学習コースから次を選ぶ