This HTML5 document contains 14 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n8http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Tardos-függvény
rdfs:label
Tardos-függvény
dct:subject
n8:Gráfinvariánsok n8:Áramköri_bonyolultság
dbo:wikiPageID
1500950
dbo:wikiPageRevisionID
19955967
prop-hu:wikiPageUsesTemplate
n11:Harvtxt n11:Portál n11:Fordítás n11:Reflist
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.
prov:wasDerivedFrom
wikipedia-hu:Tardos-függvény?oldid=19955967&ns=0
dbo:wikiPageLength
4401
foaf:isPrimaryTopicOf
wikipedia-hu:Tardos-függvény
Subject Item
wikipedia-hu:Tardos-függvény
foaf:primaryTopic
dbpedia-hu:Tardos-függvény