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 additív hibával végzi, majd -et ad az eredményhez, és így kerekít a legközelebbi egészhez. A képletben a gráf éleinek, 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[szerkeszté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[szerkesztés]
- ↑ 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/>
