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:
To define her function, Tardos uses a polynomial-time approximation scheme for the Lovász number, based on the ellipsoid method and provided by. 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, adds to the approximation, and then rounds the result to the nearest integer. Here denotes the number of edges in the given graph, and 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.