Tardos function

In graph theory and circuit complexity, the Tardos function is a graph invariant introduced by Éva Tardos in 1988 that has the following properties:^[1][2]

• Like the Lovász number of the complement of a graph, the Tardos function is sandwiched between the clique number and the chromatic number of the graph. These two numbers are both NP-hard to compute.
• The Tardos function is monotone, in the sense that adding edges to a graph can only cause its Tardos function to increase or stay the same, but never decrease.
• The Tardos function can be computed in polynomial time.
• Any monotone circuit for computing the Tardos function requires exponential size.

To define her function, Tardos uses a polynomial-time approximation scheme for the Lovász number, based on the ellipsoid method and provided by Grötschel, Lovász & Schrijver (1981).^[3] Approximating the Lovász number of the complement and then rounding the approximation to an integer would not necessarily produce a monotone function, however. To make the result monotone, Tardos approximates the Lovász number of the complement to within an additive error of ${\displaystyle 1/n^{2}}$, adds ${\displaystyle m/n^{2}}$ to the approximation, and then rounds the result to the nearest integer. Here ${\displaystyle m}$ denotes the number of edges in the given graph, and ${\displaystyle n}$ denotes the number of vertices.^[1]

Tardos used her function to prove an exponential separation between the capabilities of monotone Boolean logic circuits and arbitrary circuits. A result of Alexander Razborov, previously used to show that the clique number required exponentially large monotone circuits,^[4][5] also shows that the Tardos function requires exponentially large monotone circuits despite being computable by a non-monotone circuit of polynomial size. Later, the same function was used to provide a counterexample to a purported proof of P ≠ NP by Norbert Blum.^[6]

References[]