Tardos funktion

I grafteori och kretskomplexitet är Tardos -funktionen en grafinvariant som introducerades av Éva Tardos 1988 och som har följande egenskaper:

• Liksom Lovász-numret för komplementet till en graf är Tardos-funktionen inklämd mellan klicknumret och grafens kromatiska nummer . Dessa två tal är båda NP-svåra att beräkna.
• Tardos-funktionen är monoton, i den meningen att lägga till kanter till en graf bara kan få dess Tardos-funktion att öka eller förbli densamma, men aldrig minska.
• Tardos-funktionen kan beräknas i polynomtid .
• Varje monoton krets för att beräkna Tardos-funktionen kräver exponentiell storlek.

För att definiera sin funktion använder Tardos ett polynom-tidsapproximationsschema för Lovász-talet, baserat på ellipsoidmetoden och tillhandahållet av Grötschel, Lovász & Schrijver (1981) . Att approximera Lovász-talet för komplementet och sedan avrunda approximationen till ett heltal skulle dock inte nödvändigtvis producera en monoton funktion. För att göra resultatet monotont, approximerar Tardos Lovász-talet för komplementet inom ett additivt fel på ${\displaystyle 1/n^{2}} ,$ lägger till $m/n^{2 }$ till approximationen och avrundar sedan resultatet till närmaste heltal. Här $m$ antalet kanter i den givna grafen, och $n$ anger antalet hörn.

Tardos använde sin funktion för att bevisa en exponentiell separation mellan förmågan hos monotona booleska logiska kretsar och godtyckliga kretsar. Ett resultat av Alexander Razborov , som tidigare använts för att visa att klicktalet krävde exponentiellt stora monotona kretsar, visar också att Tardos-funktionen kräver exponentiellt stora monotona kretsar trots att den kan beräknas av en icke-monotone krets av polynomstorlek. Senare användes samma funktion för att ge ett motexempel till ett påstått bevis på P ≠ NP av Norbert Blum.