タルドス関数

グラフ理論と回路計算量において、タルドス関数は1988年にエヴァ・タルドスによって導入されたグラフ不変量であり、次のような性質を持つ: ^{[1] [2]}

• グラフの補集合のLovász 数と同様に、Tardos 関数はグラフのクリーク数と彩色数の間に挟まれます。これら 2 つの数はどちらも計算がNP 困難です。
• Tardos 関数は単調です。つまり、グラフにエッジを追加しても Tardos 関数は増加するか同じままになるだけで、減少することはありません。
• Tardos関数は多項式時間で計算できます。
• Tardos 関数を計算するための単調な回路には、指数関数的なサイズが必要です。

関数を定義するために、タルドスは、楕円体法に基づき、グロッシェル、ロヴァース、シュライバー（1981）によって提供されたロヴァース数の多項式時間近似スキームを使用しています。 ^[3]ただし、補数のロヴァース数を近似し、近似値を整数に丸めても、必ずしも単調関数が生成されるわけではありません。結果を単調にするために、タルドスは補数のロヴァース数を の加法誤差内に近似し、近似値に を加算し、結果を最も近い整数に丸めます。ここで は与えられたグラフの辺の数を表し、 は頂点の数を表します。^[1]${\displaystyle 1/n^{2}}$${\displaystyle m/n^{2}}$${\displaystyle m}$${\displaystyle n}$

タルドスは彼女の関数を使って、単調なブール論理回路と任意の回路の能力の間に指数関数的な隔たりがあることを証明した。アレクサンダー・ラズボロフの結果は、クリーク数が指数関数的に大きな単調回路を必要とすることを示すために以前使われたが、^{[4] [5] は}、タルドス関数が多項式サイズの非単調回路で計算可能であるにもかかわらず、指数関数的に大きな単調回路を必要とすることも示している。後に、同じ関数はノルベルト・ブルムによるP ≠ NPの証明とされるものに対する反例を提供するために使われた。^[6]