Funkce Tardos - Tardos function - Wikipedia

v teorie grafů a složitost obvodu, Funkce Tardos je graf neměnný představil Éva Tardos v roce 1988, který má následující vlastnosti:^[1][2]

• Jako Lovászovo číslo z doplněk grafu, funkce Tardos je vložena mezi číslo kliky a chromatické číslo grafu. Tato dvě čísla jsou obě NP-tvrdé počítat.
• Funkce Tardos je monotónní v tom smyslu, že přidání hran do grafu může způsobit, že se její funkce Tardos zvýší nebo zůstane stejná, ale nikdy se nezmenší.
• Lze vypočítat funkci Tardos polynomiální čas.
• Žádný monotónní obvod pro výpočet funkce Tardos vyžaduje exponenciální velikost.

K definování své funkce používá Tardos a schéma aproximace v polynomiálním čase pro číslo Lovász na základě elipsoidní metoda a poskytl Grötschel, Lovász & Schrijver (1981).^[3] Přibližování Lovászova čísla doplňku a následné zaokrouhlování aproximace na celé číslo by však nutně nevytvořilo monotónní funkci. Aby byl výsledek monotónní, přibližuje Tardos Lovászovo číslo doplňku v rámci aditivní chyby ${ displaystyle 1 / n ^ {2}}$, dodává ${ displaystyle m / n ^ {2}}$ na aproximaci a poté zaokrouhlí výsledek na nejbližší celé číslo. Tady ${ displaystyle m}$ označuje počet hran v daném grafu a ${ displaystyle n}$ označuje počet vrcholů.^[1]

Tardos pomocí své funkce prokázal exponenciální oddělení schopností monotónních logických obvodů logické a libovolných obvodů. Alexander Razborov, dříve používané k prokázání, že počet klik vyžaduje exponenciálně velké monotónní obvody,^[4][5] také ukazuje, že funkce Tardos vyžaduje exponenciálně velké monotónní obvody, přestože jsou vypočítatelné ne-monotónním obvodem polynomiální velikosti. Později byla stejná funkce použita k poskytnutí protiklad na údajný důkaz P ≠ NP Norbert Blum.^[6]

Reference