PPAD (složitost) - PPAD (complexity)

v počítačová věda, PPAD („Argumenty polynomiální parity na směrovaných grafech“) je a třída složitosti představil Christos Papadimitriou v roce 1994. PPAD je podtřídou TFNP na základě funkcí, které lze paritním argumentem zobrazit jako celkem.[1][2] Třída přilákala významnou pozornost v oblasti teorie algoritmických her protože obsahuje problém výpočtu a Nashova rovnováha: tento problém se ukázal jako úplný pro PPAD od Daskalakise, Goldberga a Papadimitrioua s alespoň 3 hráči a později rozšířený Chenem a Dengem na 2 hráče.[3][4]

Definice

PPAD je podmnožinou třídy TFNP, třída funkční problémy v FNP které zaručeně budou celkový. The TFNP formální definice je uvedena následovně:

Binární relace P (X,y) je v TFNP právě tehdy, pokud existuje deterministický polynomiální časový algoritmus, který může určit, zda P (X,y) drží dané oba X a ya pro každého X, existuje a y takový, že P (X,y) drží.

Podtřídy TFNP jsou definovány na základě typu matematického důkazu použitého k prokázání, že řešení vždy existuje. Neformálně je PPAD podtřídou TFNP, kde záruka, že existuje y takový, že P (X,y) drží je založen na paritním argumentu v orientovaném grafu. Třída je formálně definována zadáním jednoho z jejích úplných problémů, známého jako Konec řádku:

G je (možná exponenciálně velký) směrovaný graf bez izolovaných vrcholů a se všemi vrchol mající nanejvýš jednoho předchůdce a jednoho následníka. G je specifikováno poskytnutím polynomiálně-časově vypočítatelné funkce f (proti) (polynom o velikosti proti), který vrací předchůdce a následníka (pokud existují) vrcholu proti. Vzhledem k vrcholu s v G bez předchůdce najděte vrchol t ≠ s bez předchůdce ani bez nástupce. (Vstupem do problému je vrchol zdroje s a funkce f (proti)). Jinými slovy, chceme jakýkoli jiný zdroj nebo jímku směrovaného grafu než s.

Takový t musí existovat, pokud s ano, protože struktura G znamená, že vrcholy pouze s jedním sousedem přicházejí ve dvojicích. Zejména vzhledem k tomu s, můžeme najít takové t na druhém konci řetězce začínajícím na s. (Všimněte si, že to může trvat exponenciální čas, pokud budeme opakovaně vyhodnocovat f.)

Vztah k dalším třídám složitosti

PPAD je obsažen v (ale není známo, že by se rovnal) PPA (odpovídající třída paritních argumentů pro neorientovaný grafy), který je obsažen v TFNP. PPAD je také obsažen v (ale není známo, že by se rovnal) PPP, další podtřída TFNP. Obsahuje CLS.[5]

PPAD je třída problémů, o nichž se věří, že jsou těžké, ale získání úplnosti PPAD je slabším důkazem neřešitelnosti než získání NP-úplnost. Problémy PPAD nemohou být NP úplné, z technického důvodu, že NP je třídou problémů s rozhodováním, ale odpověď na problémy PPAD je vždy ano, protože je známo, že existuje řešení, i když by mohlo být těžké toto řešení najít.[6] PPAD a NP však spolu úzce souvisejí. Zatímco otázka, zda pro danou hru existuje Nashova rovnováha, nemůže být NP-těžká, protože odpověď je vždy ano, otázka, zda druhý rovnováha existuje, je NP úplná.[7] Stále se může stát, že PPAD je stejné třídy jako FP, a stále to mít P ≠ NP, i když se to zdá nepravděpodobné.[Citace je zapotřebí ] Mezi příklady úplných problémů PPAD patří hledání Nashovy rovnováhy, výpočet pevných bodů ve Windows Brouwer funkce, hledání Arrow-Debreuovy rovnováhy na trzích.[8]

Jiné pozoruhodné úplné problémy

Hlavní článek: Seznam úplných problémů s PPAD

Reference

  1. ^ Christos Papadimitriou (1994). „O složitosti argumentu parity a dalších neúčinných důkazech existence“ (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016 / S0022-0000 (05) 80063-7. Archivovány od originál (PDF) dne 04.03.2016. Citováno 2008-03-08.
  2. ^ Fortnow, Lance (2005). „Co je PPAD?“. Citováno 2007-01-29.
  3. ^ A b *Chen, Xi; Deng, Xiaotie (2006). Vyřešení složitosti Nashovy rovnováhy pro dva hráče. Proc. 47. Symp. Základy informatiky. 261–271. doi:10.1109 / FOCS.2006.69. ECCC  TR05-140..
  4. ^ Daskalakis, Constantinos .; Goldberg, Paul W .; Papadimitriou, Christos H. (01.01.2009). „Složitost výpočtu Nashovy rovnováhy“. SIAM Journal on Computing. 39 (1): 195–259. doi:10.1137/070699652. ISSN  0097-5397.
  5. ^ Daskalakis, C .; Papadimitriou, C. (2011-01-23). Kontinuální místní vyhledávání. Řízení. Společnost pro průmyslovou a aplikovanou matematiku. str. 790–804. CiteSeerX  10.1.1.362.9554. doi:10.1137/1.9781611973082.62. ISBN  9780898719932.
  6. ^ Scott Aaronson (2011). "Proč by se filozofové měli starat o výpočetní složitost". arXiv:1108.1791 [cs.CC ].
  7. ^ Christos Papadimitriou (2011). „Přednáška: Složitost hledání Nashovy rovnováhy“ (PDF).
  8. ^ A b C. Daskalakis, P.W. Goldberg a C.H. Papadimitriou (2009). "Složitost výpočtu Nashovy rovnováhy". SIAM Journal on Computing. 39 (3): 195–259. CiteSeerX  10.1.1.152.7003. doi:10.1137/070699652.
  9. ^ Xi Chen a Xiaotie Deng (2006). "O složitosti 2D diskrétního problému s pevným bodem". Mezinárodní kolokvium o automatech, jazycích a programování. 489–500. ECCC  TR06-037.
  10. ^ Deng, X .; Qi, Q .; Saberi, A. (2012). „Algoritmická řešení pro řezání dortů bez závisti“. Operační výzkum. 60 (6): 1461. doi:10.1287 / opre.1120.1116.