Tardos function

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 . 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 1/n^2 , adds m/n^2 to the approximation, and then rounds the result to the nearest integer. Here m denotes the number of edges in the given graph, and n denotes the number of vertices.…

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 . 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 1/n^2 , adds m/n^2 to the approximation, and then rounds the result to the nearest integer. Here m denotes the number of edges in the given graph, and 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374345209 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374345209 · captured 1789123486.0 · version history

Cite this page as: encyclopegia.org, “Tardos function”, snapshot enwiki-001374345209. https://encyclopegia.org/a/tardos-function

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.