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]

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 , 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.[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. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.