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).[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 [math]\displaystyle{ 1/n^2 }[/math], adds [math]\displaystyle{ m/n^2 }[/math] to the approximation, and then rounds the result to the nearest integer. Here [math]\displaystyle{ m }[/math] denotes the number of edges in the given graph, and [math]\displaystyle{ n }[/math] 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
- ↑ 1.0 1.1 "The gap between monotone and nonmonotone circuit complexity is exponential", Combinatorica 8 (1): 141–142, 1988, doi:10.1007/BF02122563, http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf
- ↑ Jukna, Stasys (2012), Boolean Function Complexity: Advances and Frontiers, Algorithms and Combinatorics, 27, Springer, p. 272, ISBN 9783642245084, https://books.google.com/books?id=rHn7hXxyPAkC&pg=PA272
- ↑ "The ellipsoid method and its consequences in combinatorial optimization", Combinatorica 1 (2): 169–197, 1981, doi:10.1007/BF02579273.
- ↑ "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR 281 (4): 798–801, 1985
- ↑ "The monotone circuit complexity of Boolean functions", Combinatorica 7 (1): 1–22, 1987, doi:10.1007/BF02579196
- ↑ Trevisan, Luca (August 15, 2017), "On Norbert Blum's claimed proof that P does not equal NP", in theory, https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/
![]() | Original source: https://en.wikipedia.org/wiki/Tardos function.
Read more |