coNPとは何か｜Noであることの短い証拠

coNPとは、「属さない（Noである）」ことを短い証拠で多項式時間検証できる問題のクラスである。形式的には、補集合がNPに属するとき、元のクラスはcoNPに入る。

NPがYesの短い証明書を扱うのに対し、coNPはNoの短い証明書を扱う。両方できるとき、問題はNP ∩ coNPに入る。

NPとcoNPの非対称

Pの定義は対称である。属するかを速く判定できるなら、属さないことも同じく速い。すなわちP = coPである。一方NPの定義は非対称である。Yesの短い証明書があっても、Noの短い証明書が自動的に従うわけではない。

標準予想はNP ≠ coNPである。未証明である。

具体例

SATは、充足割当を一つ提示すればYesを検証できる。対になるトートロジー判定では、すべての割当で真かを問う。あることの証明と、ないことの証明は対称とは限らない。

素数判定は、かつてNPとcoNPの両側から特徴づけられる問題として注目され、その後 Manindra Agrawal（マニンドラ・アグラワル、1966–）、Neeraj Kayal（ニーラジ・カヤル、1979–）、Nitin Saxena（ニティン・サクセナ、1981–）による AKS素数判定法（2002年）によりPに属することが示された。検証しやすい特徴づけを見つけることが、効率的な判定手続につながる場合がある。ただし、NP ∩ coNPのすべてがPに入るかは未解決である。（P=NP予想またはP≠NP予想）

素因数分解や離散対数は、長いあいだNP ∩ coNPに見えるがPとの関係が未解決な例として議論されてきた。

よい特徴づけ

Jack Edmonds（ジャック・エドモンズ、1934–）のいう good characterization（よい特徴づけ）は、YesとNoの両方に短い証拠がある状態に近い。経営へ応用するなら、「採用理由」だけでなく「棄却理由」も短い証跡で示せることである。これは手続の写像であり、クラス包含の証明ではない。

欲しい理由だけを増やすと過学習に近づく。欲しくない理由（衝突項）を数え、No側の証拠を短く保つ方が、検証可能性が高い。

包含関係

既知の包含は次のとおりである。

P ⊆ NP ∩ coNP ⊆ NP

および

P ⊆ NP ∩ coNP ⊆ coNP

NPとcoNPのどちらが大きいか、交わりがPに一致するかは未解決である。

実務への読み替え

採用だけを長く説明し、棄却を曖昧にすると、組織はNP側に偏る。棄却の短い証拠（Hard違反、学習節、Bound内反例）を残すことが、coNP側の運用に相当する。

混同してはならない点

• coNPは「計算不可能」ではない
• Noの証拠が短いことと、探索が簡単であることは別である
• NP ∩ coNPに入っても、直ちにPであるとは限らない

coNPの有効性は、否定を感情で済ませないことではなく、YesだけでなくNoを短い証拠で検証できる形へ判定問題を書き換えることにある。

PHとの関係

PH（Polynomial Hierarchy／多項式階層）とは、NP・coNPを底に、限量記号（∃＝「ある」、∀＝「すべて」）の交代回数で階層を積む複雑性クラスの族である。この交代が資源になる。SATは∃でNP側、トートロジーは∀でcoNP側に対応する。∃∀や∀∃へ進むとΣ₂、Π₂などへ広がる。coNPは、その最初のΠ側（∀側）である。

読み方の凡例：Σ（シグマ）は∃から始まる側、Π（パイ）は∀から始まる側。下付きの数字は限量記号の交代段数である。

事業で∀（すべて）の範囲を増やすほど、「すべての顧客・すべてのシナリオで」を証明しなければならなくなり、No側の証拠が長くなる。限量記号を増やす前に、Noを短く示せる形へ問題を落とす。

『P vs NP経営』の詳細はこちら https://link.amazon/B04IEdYsn