タルドス関数

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

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

タルドスは関数を定義するために、楕円体法に基づき、Grötschel、Lovász、Schrijver (1981) によって提供されたロヴァース数の多項式時間近似スキームを用いている。 ^[3]しかし、補グラフのロヴァース数を近似し、その近似値を整数に丸めても、必ずしも単調関数になるわけではない。結果を単調にするために、タルドスは補グラフのロヴァース数を の加法誤差以内に近似し、近似値に を加算し、その結果を最も近い整数に丸める。ここで は与えられたグラフの辺の数、 は頂点の数を表す。^[1]${\displaystyle 1/n^{2}}$ ${\displaystyle m/n^{2}}$ ${\displaystyle m}$ ${\displaystyle n}$

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

参考文献

1. Tardos, É. (1988)、「単調回路と非単調回路の複雑さの差は指数関数的である」(PDF)、Combinatorica、8 (1): 141– 142、doi :10.1007/BF02122563、MR  0952004
2. Jukna, Stasys (2012), ブール関数の複雑性：進歩と最前線、アルゴリズムと組合せ論、第27巻、Springer、p. 272、ISBN 9783642245084
3. Grötschel, M. ; Lovász, L. ; Schrijver, A. (1981)、「楕円体法と組み合わせ最適化におけるその帰結」、Combinatorica、1 (2): 169– 197、doi :10.1007/BF02579273、MR  0625550。
4. Razborov, AA (1985)、「いくつかのブール関数の単調複雑度の下限」、Doklady Akademii Nauk SSSR、281 (4): 798– 801、MR  0785629
5. アロン、N. ; Boppana、RB (1987)、「ブール関数の単調回路の複雑さ」、Combinatorica、7 (1): 1–22、CiteSeerX 10.1.1.300.9623、doi :10.1007/BF02579196、MR  0905147 
6. トレヴィサン、ルカ（2017年8月15日）「PがNPと等しくないというノーバート・ブルムの主張する証明について」、理論的には