Tardos-függvény

A matematika, azon belül a gráfelmélet és a kombinatorikus bonyolultság területén az 1988-ban Tardos Éva által bevezetett Tardos-függvény a következő tulajdonságokkal rendelkező gráfinvariáns:^[1]^[2]

A gráf komplementerének Lovász-számához hasonlóan a Tardos-függvény értéke is a gráf klikkszáma és kromatikus száma között van. Mindkét érték kiszámítása NP-nehéz feladat.
A Tardos-függvény monoton, abban az értelemben, hogy egy gráfhoz éleket hozzáadva a Tardos-függvényérték növekszik vagy állandó marad, de sohasem csökken.
A Tardos-függvény értéke polinom időben meghatározható.
A Tardos-függvényt kiszámító bármely monoton áramkörnek (csak ÉS és VAGY kapukat tartalmazó áramkörnek) exponenciális méretűnek kell lennie.

A függvényérték meghatározásához Tardos a (Grötschel, Lovász & Schrijver 1981) által megadott ellipszoid-módszerre épülő polinomiális approximációs sémával közelíti a Lovász-számot.^[3] A komplementer gráf Lovász-számának approximációja után a legközelebbi egész számra kerekítés nem feltétlenül eredményezne monoton függvényt. A monotonitás elérése céljából Tardos az approximációt $1/n^{2}$ additív hibával végzi, majd $m/n^{2}$ -et ad az eredményhez, és így kerekít a legközelebbi egészhez. A képletben $m$ a gráf éleinek, $n$ a csúcsainak számát jelöli.^[1]

A Tardos-függvény megalkotásának motivációja annak megmutatása volt, hogy a monoton Boole-áramkörök és a tetszőleges logikai kapukat használó Boole-áramkörök lehetőségei között exponenciális szakadék húzódik. Alekszandr Razborov egy eredményének segítségével korábban megmutatták, hogy a klikkszám meghatározásához exponenciálisan nagy monoton Boole-áramkörökre van szükség^[4]^[5] – ugyanebből az eredményből kiindulva az is belátható, hogy a Tardos-függvény kiszámításához is exponenciális méretű monoton áramkörökre van szükség, annak ellenére, hogy nem monoton áramkörből polinom méretű is elegendő lenne. Később ez a függvény szolgált a Norbert Blum által 2017-ben adott P ≠ NP bizonyítással szembeni ellenpéldául.^[6]

Fordítás

Ez a szócikk részben vagy egészben a Tardos function című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ ^a ^b Tardos, É. (1988), "The gap between monotone and nonmonotone circuit complexity is exponential", Combinatorica 8 (1): 141–142, 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, vol. 27, Algorithms and Combinatorics, Springer, p. 272, ISBN 9783642245084, <https://books.google.com/books?id=rHn7hXxyPAkC&pg=PA272>
↑ 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.
↑ Razborov, A. A. (1985), "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR 281 (4): 798–801
↑ Alon, N. & Boppana, R. B. (1987), "The monotone circuit complexity of Boolean functions", Combinatorica 7 (1): 1–22, DOI 10.1007/BF02579196
↑ Trevisan, Luca (August 15, 2017), On Norbert Blum’s claimed proof that P does not equal NP, <https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/>

Matematikaportál • összefoglaló, színes tartalomajánló lap

[e-1] Tardos, É. (1988), "The gap between monotone and nonmonotone circuit complexity is exponential", Combinatorica 8 (1): 141–142, doi:10.1007/BF02122563, <http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf>

[2] Jukna, Stasys (2012), Boolean Function Complexity: Advances and Frontiers, vol. 27, Algorithms and Combinatorics, Springer, p. 272, ISBN 9783642245084, <https://books.google.com/books?id=rHn7hXxyPAkC&pg=PA272>

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

[4] Razborov, A. A. (1985), "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR 281 (4): 798–801

[5] Alon, N. & Boppana, R. B. (1987), "The monotone circuit complexity of Boolean functions", Combinatorica 7 (1): 1–22, DOI 10.1007/BF02579196

[6] Trevisan, Luca (August 15, 2017), On Norbert Blum’s claimed proof that P does not equal NP, <https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/>

[1]

[2]

[3]

[4]

[5]

[6]