マハニーの定理

マハニーの定理は、スティーブン・マハニーによって証明された計算複雑性理論の定理であり、次のように述べている。

疎言語がNP困難であれば、P=NPとなる。^{[ 1 ]}

NP困難な疎集合の存在は、NP完全な疎集合の存在を意味することに注意されたい。^{[ 2 ]} マハニーの定理は、バーマン・ハートマニス予想に触発されたものである。

任意の2つのNP完全集合が与えられた場合${\displaystyle A,B}$関数のペアが存在する${\displaystyle f:A\to B,f^{-1}:B\to A}$これらは互いに逆関数であり、多項式時間で計算可能である。

NP完全集合の中には疎でないものがあることがわかっているので（例えば、充足可能な3SAT式の集合など）、バーマンとハートマニスは、より弱い第二の予想を導き出した。

NP完全な疎集合は存在しない。

Mahaneyの結果は、P≠NPならば確かにNP完全な疎集合は存在しないことを示しており、P≠NPという標準的な仮定の下で2番目の予想を解決している。この結果は1991年に強化され、次のように述べられた。^{[ 3 ]}

疎言語が存在し、その疎言語オラクルに対して O(1) 回のクエリを実行することで SAT 問題を解く多項式時間アルゴリズムが存在するならば、P=NP である。

これは、多項式時間アルゴリズムが疎言語プロトコルに対して最大で1回のクエリしか行えないという特殊なケースであるマハニーの定理よりも強力です。