バーマン・ハートマニス予想

形式言語L ₁とL ₂の間の同型写像は、 L ₁のアルファベットの文字列からL ₂のアルファベットの文字列への全単射写像fであり、文字列xがL ₁に属するのは、 f ( x ) がL ₂に属する場合のみであるという性質を持つ。

多項式時間同型写像、または略してp同型写像とは、関数fとその逆関数の両方を、それぞれの引数の長さの多項式時間で計算できるような同型写像fのことである。

バーマンとハートマニスは、すべてのNP完全言語は互いにp同型であると推測した。^{[ 1 ]}

形式言語Lは、多項式時間関数f ( x , y ) とその多項式時間逆関数が存在し、すべてのxとすべてのyに対して、文字列x がLに属するのはf ( x , y ) がLに属する場合のみであるような場合、パディング可能である。つまり、入力xに無関係な情報yを可逆的にパディングしても、言語への所属は変わらない。バーマンとハートマニスは、パディング可能な NP 完全言語のすべてのペアが p-同型であることを証明した。 ^{[ 1 ]}

p同型性はパディング可能性を保持し、パディング可能なNP完全言語が存在するため、バーマン・ハートマニス予想を同等に表現すると、すべてのNP完全言語はパディング可能であるということになる。

多項式時間同型性は同値関係であり、形式言語を同値類に分割するために使用できるため、バーマン・ハートマニス予想を別の言い方で述べると、NP完全言語はこの関係に関して単一の同値類を形成することになる。

形式言語は、長さnの yes インスタンスの数がnの関数として多項式的にしか増加しない場合にスパースであると呼ばれる。既知の NP 完全言語は、指数関数的に増加する yes インスタンスの数を持ち、指数関数的に多くの yes インスタンスを持つ言語Lは、1 対 1 のマッピングを行うためには yes インスタンスを多項式よりも長い文字列にマッピングする必要があるため、スパース言語とp型同型にはなり得ない。したがって、バーマン・ハートマニス予想が正しい場合、スパースな NP 完全言語は存在しないという直接的な結果が生じる。

疎な NP 完全言語が存在しないということは、P ≠ NP であることを意味します。なぜなら、P = NP であれば、P に含まれるすべての非自明な言語 (すべてのビットがゼロであるバイナリ文字列の言語など、疎な言語も含む) は NP 完全になるからです。1982 年に、スティーブ・マハニーは、疎な NP 完全言語が存在しないことは (多対一還元を用いた標準的な方法で NP 完全性を定義した場合) は実際には P ≠ NP という主張と同等であるという証明を発表しました。これがマハニーの定理です。チューリング還元を用いた NP 完全性の緩和された定義であっても、疎な NP 完全言語の存在は、多項式階層の予期せぬ崩壊を意味します。^{[ 6 ]}