| dbo:abstract
|
- A matematika, azon belül a gráfelmélet és a 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 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 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 meghatározható.
* A Tardos-függvényt kiszámító bármely (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 épülő 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. 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 bizonyítással szembeni ellenpéldául. (hu)
- A matematika, azon belül a gráfelmélet és a 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 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 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 meghatározható.
* A Tardos-függvényt kiszámító bármely (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 épülő 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. 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 bizonyítással szembeni ellenpéldául. (hu)
|
