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: 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 által megadott ellipszoid-módszerre épülő polinomiális approximációs sémával közelíti a Lovász-számot.. 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.
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 – 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.
Fordítás
Jegyzetek
Kategória:Gráfinvariánsok Kategória:Áramköri bonyolultság