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に入るかは未解決である。

素因数分解や離散対数は、長いあいだ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では、限量記号の交代が資源になる。SATは∃でNP側、トートロジーは∀でcoNP側に対応する。∃∀や∀∃へ進むとΣ₂、Π₂などへ広がる。coNPは、その最初のΠ側である。

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

棄却理由の短い証拠の例

• Bound内に現金下限割れの反例経路がある（BMCのSAT）
• 学習済み禁止節に再訪した
• Hardな法令・安全条件を破る
• 二者間の二項制約がImplication Graph上で矛盾する

これらは感情的な「好きではない」より短い。記録可能で、第三者検証に耐える。

NP ∩ coNPを目指す設計

採用理由と棄却理由の両方を短くできる問題設計は、よい特徴づけに近い。価格・品質・在庫の採否を、長い物語ではなく、固定したHardと証跡で示す。両方できない領域は、探索を広げず、問題設定を見直す。

コミュニケーションとしてのNo

数学コミュニティは、命題にYes/Noで応答する証明形式でコミュニケーションする。公理を共有しているから、毎回の前提説明を省略できる。組織のNoも同様で、共有Hardが無いと、棄却が人格攻撃に見える。

Noの短い証拠を先に設計しておくと、議論は人格から手続へ戻る。これがcoNP的運用の実務的意味である。

運用への落とし込み

棄却票には必ず短い根拠欄を付ける。根拠欄が空の棄却は無効とする。根拠の型を、Hard違反、Bound内反例、学習節再訪、二項矛盾の四種に制限する。自由記述の長文は添付に回し、本体は型付きの短い証拠だけにする。

これにより、No側の検証時間が読み手に対して多項式的に収まる。四半期ごとに、根拠型の分布を集計する。自由記述添付ばかり増える部署は、Hard定義が不足している。採用票にも対称に、Yesの短い証拠欄を置く。片方だけ短い組織は、検証可能性が歪む。

採否の対称化

採用会議と棄却会議を別文化にしない。同じ票様式、同じ根拠型、同じ保存期間にする。採用だけが長く、棄却だけが短い、またはその逆は、クラスが歪んでいる印である。四半期で、Yes証拠の平均文字数とNo証拠の平均文字数を並べ、乖離が大きい部署を見直す。短さは善だが、空は悪である。

まとめに代えて

Yesの物語が長い組織ほど、Noが人格化する。coNPの視点は、棄却を短い証拠へ圧縮する設計を求める。BMCの反例、CDCLの学習節、二項制約の矛盾、Hard違反のログは、その候補である。NP ∩ coNPに近い運用は、採否の両方を第三者が追える状態である。未解決の理論予想を、現場のスローガンにしない。使えるのは、対称でない検証可能性という認識と、No側の証跡を残す習慣である。

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