Misplaced Pages

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

• 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). 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.

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, 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.

References

1. ^ Tardos, É. (1988), "The gap between monotone and nonmonotone circuit complexity is exponential" (PDF), Combinatorica, 8 (1): 141–142, doi:10.1007/BF02122563, MR 0952004
2. Jukna, Stasys (2012), Boolean Function Complexity: Advances and Frontiers, Algorithms and Combinatorics, vol. 27, Springer, p. 272, ISBN 9783642245084
3. Grötschel, M.; Lovász, L.; Schrijver, A. (1981), "The ellipsoid method and its consequences in combinatorial optimization", Combinatorica, 1 (2): 169–197, doi:10.1007/BF02579273, MR 0625550.
4. Razborov, A. A. (1985), "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR, 281 (4): 798–801, MR 0785629
5. Alon, N.; Boppana, R. B. (1987), "The monotone circuit complexity of Boolean functions", Combinatorica, 7 (1): 1–22, CiteSeerX 10.1.1.300.9623, doi:10.1007/BF02579196, MR 0905147
6. Trevisan, Luca (August 15, 2017), "On Norbert Blum's claimed proof that P does not equal NP", in theory

• Graph invariants
• Circuit complexity