Aanderaa-Karp-Rosenbergova hypotéza

Nevyřešené problémy informatiky : Dokažte nebo vyvřete domněnku Aanderaa-Karp-Rosenberg.

Aandera-Karp-Rosenbergova hypotéza (také známá jako Aandera-Rosenbergova hypotéza nebo hypotéza obtížnosti ) je skupina souvisejících hypotéz o počtu otázek ve tvaru "Existuje hrana mezi vrcholem u a vrcholem v ?", která musí být zodpovězen, abyste určili, zda má nebo nemá neorientovaný graf určitou vlastnost (invariantní), jako je rovinný nebo bipartitní . Hypotéza je pojmenována podle norského matematika Stola Aanderaa a amerických vědců Richarda M. Karpa a Arnolda L. Rosenberga. Podle hypotézy pro širokou třídu invariantů žádný algoritmus nemůže zaručit, že algoritmus může vynechat jakýkoli dotaz – jakýkoli algoritmus pro určení, zda má graf nějakou vlastnost, bez ohledu na to, jak chytrý je tento algoritmus, musí zkontrolovat každý pár vrcholů předtím. dává odpověď. Vlastnost, která hypotézu splňuje, se nazývá hard .

Přesněji řečeno, Aandera-Rosenbergova domněnka říká, že jakýkoli deterministický algoritmus musí testovat alespoň pevný zlomek všech možných dvojic vrcholů, aby v nejhorším případě určil netriviální monotónní vlastnost grafu. V tomto kontextu je vlastnost monotónní, pokud zůstává pravdivá při přidávání hran (takže vlastnost rovinnosti není monotónní, ale vlastnost nerovinnosti je monotónní). Přesnější verze této domněnky, nazvaná hypotéza obtížnosti nebo Aandera-Karp-Rosenbergova domněnka, uvádí, že přesně testy jsou potřeba. Byly formulovány a studovány verze problému pro pravděpodobnostní a kvantové algoritmy. ${\tfrac {n(n-1)}{2))$

Deterministická Aanderaa-Rosenbergova domněnka byla prokázána Rivestem a Willeminem [1] , ale silnější Aanderaa-Karp-Rosenbergova domněnka zůstává neprokázaná. Existuje také velký rozdíl mezi dolní hranicí a nejlépe prokázanou dolní hranicí pravděpodobnostní a kvantové složitosti podle počtu dotazů.

Příklad

Vlastnost nebýt prázdná (tj. mít alespoň jednu hranu) je monotónní, protože přidáním další hrany k neprázdnému grafu vznikne neprázdný graf. Existuje jednoduchý algoritmus pro testování, zda je graf neprázdný - projděte všechny dvojice vrcholů a zkontrolujte, zda je každý pár spojen hranou. Pokud je hrana takto nalezena, přerušíme smyčku a oznámíme, že graf není prázdný, a pokud smyčka skončí bez nalezení jakékoli hrany, pak oznámíme, že graf je prázdný. Na takových grafech (například úplných grafech ) se tento algoritmus rychle ukončí bez kontroly každé dvojice vrcholů, ale na prázdném grafu algoritmus před ukončením zkontroluje všechny možné dvojice. Proto je složitost algoritmu pro dotazy stejná - v nejhorším případě algoritmus provádí kontroly. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Výše popsaný algoritmus není jedinou možnou metodou pro kontrolu neprázdnosti, ale z Aandera-Karp-Rosenbergovy domněnky vyplývá, že každý determinantní algoritmus pro kontrolu neprázdnosti má stejnou složitost dotazu . To znamená, že vlastnost být neprázdná je obtížná . Pro tuto vlastnost je snadné přímo zkontrolovat výsledek - pokud algoritmus neprovádí kontroly, nebude schopen rozlišit mezi prázdným grafem a grafem obsahujícím jednu hranu nezaškrtnuté dvojice vrcholů a musí dát nesprávnou odpověď pro jeden z těchto dvou grafů (buď pro prázdný nebo pro graf s hranou ). ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Definice

Pro účely tohoto článku budou všechny grafy jednoduché a neorientované , pokud není uvedeno jinak. To znamená, že hrany grafu tvoří množinu (ale ne multimnožinu ) a konce každé hrany tvoří dvojice odlišných vrcholů. Předpokládá se, že grafy mají implicitní reprezentaci , ve které má každý vrchol jedinečný identifikátor nebo štítek a ve kterém lze kontrolovat sousedství dvou vrcholů, ale v grafu sousedství lze provádět pouze základní operace.

Neformálně je vlastnost grafu (nebo invariant grafu, oba termíny se v tomto článku používají zaměnitelně) vlastností grafu, která je nezávislá na označení. Formálněji je vlastnost grafu mapování z množiny všech grafů na {0,1} tak, aby se izomorfní grafy mapovaly na stejnou hodnotu. Například vlastnost obsahovat alespoň jeden vrchol stupně 2 je invariantní graf, ale vlastnost, že první vrchol má stupeň 2, není invariantní grafu, protože vlastnost závisí na označení grafu (zejména závisí na tom, který vrchol je považován za "první"). Invariant grafu se nazývá netriviální, pokud nemá stejnou hodnotu pro všechny grafy. Například vlastnost být grafem je triviální vlastnost, protože tuto vlastnost mají všechny grafy. Ale na druhou stranu, vlastnost být prázdný je netriviální, protože prázdný graf tuto vlastnost má, ale neprázdný ne. O vlastnosti grafu se říká, že je monotónní , pokud přidání hran vlastnosti nezničí. Alternativně, pokud má graf monotónní vlastnost, pak má tuto vlastnost také jakýkoli supergraf tohoto grafu na stejné sadě vrcholů. Například vlastnost být nerovinný je monotónní – supergraf nerovinného grafu je také nerovinný. Vlastnost být pravidelný však není monotónní.

Zápis "O" se často používá pro složitost dotazu . Stručně řečeno, f ( n ) je pokud pro jakoukoli dostatečně velké pro nějakou kladnou konstantu c . Podobně f ( n ) je if pro dostatečně velké pro nějakou kladnou konstantu c . Nakonec f ( n ) je , pokud je zároveň , a . $O(g(n))$ $nf(n)\leqslant cg(n)$ $\Omega (g(n)}$ $nf(n)\geqslant cg(n)$ $\Theta (g(n)$ $O(g(n))$ $\Omega (g(n)}$

Složitost požadavku

Složitost deterministického dotazu pro vyhodnocení funkce n bitů se rovná počtu bitů x i , které musí deterministický algoritmus v nejhorším případě přečíst, aby určil hodnotu funkce. Pokud například funkce nabývá hodnoty 0, pokud jsou všechny bity 0 a jinak hodnota 1 (tj. funkce OR ), pak je složitost deterministických dotazů přesně n . V nejhorším případě bude prvních n − 1 přečtených bitů 0 a hodnota funkce bude záviset pouze na posledním bitu. Pokud algoritmus nepřečte tento bit, může dát nesprávnou odpověď. Počet přečtených bitů se také nazývá počet požadavků provedených na vstupu. Lze si představit, že algoritmus požádá (vykoná požadavek) na vstup o konkrétním bitu a vstup na tento požadavek odpoví. $(x_{1},x_{2},\tečky ,x_{n})$

Složitost požadavku na pravděpodobnostní funkci je definována podobně, kromě toho, že algoritmus může být pravděpodobnostní, to znamená, že si může hodit mincí a použít vrženou stranu mince k rozhodnutí, který bit požadovat. Pravděpodobnostní algoritmus však musí i nadále poskytovat správné odpovědi na všechny vstupní požadavky – chyby nejsou povoleny. Takové algoritmy se nazývají algoritmy Las Vegas a měly by být odlišeny od algoritmů Monte Carlo , ve kterých jsou povoleny některé chyby. Složitost pravděpodobnostního dotazu lze definovat ve smyslu Monte Carlo, ale Aandera-Karp-Rosenbergova domněnka hovoří o složitosti dotazů na grafové invarianty ve smyslu Las Vegas.

Kvantová složitost dotazů je přirozeným zobecněním složitosti pravděpodobnostního dotazu, přirozeně s rozlišením kvantových dotazů a odpovědí. Složitost kvantového dotazu lze také definovat pomocí algoritmů Monte Carlo nebo algoritmů Las Vegas, ale obvykle se myslí kvantové algoritmy Monte Carlo.

V kontextu této hypotézy je vypočítaná funkce vlastností grafu a vstupem je řetězec velikosti , který udává umístění hran na grafu s n vrcholy, protože graf může mít maximálně hran. Složitost požadavku na jakoukoli funkci je shora omezena hodnotou , protože po požadavcích bude načten celý vstup , který určuje celý vstupní graf. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Složitost deterministických dotazů

Pro deterministické algoritmy navrhl Rosenberg [2] , že pro všechny netriviální vlastnosti grafů na n vrcholech vyžaduje rozhodování, zda má graf tuto vlastnost, dotazy. Je jasné, že je vyžadována netriviální podmínka, protože existují triviální vlastnosti jako „je to graf?“, na které lze odpovědět bez jakéhokoli dotazu. $\Omega (n^{2})$

Hypotézu vyvrátil Aanderaa, který navrhl vlastnost orientovaného grafu (vlastnost mít „sink“), jejíž ověření vyžaduje pouze O( n ) dotazů. Propad v orientovaném grafu je vrchol, který má in-stupeň n -1 a out-stupeň 0 [3] . Tuto vlastnost lze zkontrolovat v méně než 3n dotazech [4] . Vlastností neorientovaného grafu, kterou lze ověřit v dotazech O( n ), je vlastnost „graf je graf štíra“, poprvé popsaná v Best, van Emde Boas a Lenstra [4] . Scorpion graf je graf obsahující cestu sestávající ze tří vrcholů tak, že jeden koncový vrchol cesty je spojen se všemi ostatními vrcholy grafu, zatímco dva zbývající vrcholy cesty jsou spojeny pouze s vrcholy samotné cesty. .

Poté Aanderaa a Rosenberg zformulovali novou domněnku ( Aanderaa-Rosenbergova hypotéza ), která říká, že rozhodnutí, zda má graf netriviální monotónní vlastnost, vyžaduje dotazy [5] . Tuto domněnku vyřešili Raivest a Vuillemin [1] , kteří ukázali, že k testování jakékoli netriviální monotónní vlastnosti je zapotřebí alespoň dotazů. Hranice byla později vylepšena na Kleitmana a Kwiatkowského [6] , dále na Kahna, Sachse a Sturtevanta [7] , na Kornefela a Trish [8] a na Scheiderweilera a Trish [9] . $\Omega (n^{2})$ ${\tfrac {n^{2}}{16}}$ ${\tfrac {n^{2}}{9}}$ ${\tfrac {n^{2}}{4}}-o(n^{2})$ ${\tfrac {8}{25}}n^{2}-o(n^{2})$ ${\tfrac {n^{2}}{3}}-o(n^{2})$

Richard Karp učinil přesnější tvrzení (nyní nazývané domněnka tvrdosti nebo Aandera–Karp–Rosenbergova domněnka ), že „jakákoli netriviální monotónní vlastnost grafů na n vrcholech je těžká“ [10] . O vlastnosti se říká , že je těžká , pokud určení, zda má graf danou vlastnost, vyžaduje dotazy [11] . Tato domněnka říká, že nejlepším algoritmem pro testování jakékoli netriviální monotónní vlastnosti je (v nejhorším případě) dotazovat se na všechny možné hrany. Tato domněnka zůstává otevřená, ačkoli některé speciální vlastnosti grafů se ukázaly být obtížné pro všechny n . Dohad byl vyřešen pro případ, kdy n je mocnina prvočísla , Kahn, Sacks a Sturtevant [7] pomocí topologického přístupu. Dohadu pro všechny netriviální monotónní vlastnosti bipartitních grafů vyřešil Yao [12] . Bylo také ukázáno, že pro velké n jsou také obtížné vlastnosti minor-uzavřené [13] . ${\tfrac {n(n-1)}{2))$

Složitost pravděpodobnostního dotazu

Richard Karp také předpokládal, že k testování netriviálních vlastností monotonie jsou vyžadovány dotazy, i když jsou povoleny pravděpodobnostní algoritmy. Není známa žádná netriviální vlastnost, která vyžaduje méně dotazů ke kontrole. Lineární dolní mez (to znamená pro všechny monotónní vlastnosti vyplývá z velmi obecného vztahu mezi pravděpodobnostními a deterministickými složitostmi dotazů . První superlineární dolní mez pro všechny monotónní invarianty byla dána Yao [14] , který ukázal, že Poté byl King [15] vylepšen na , a poté Hainal [16] na , Tento výsledek byl poté vylepšen na současnou dobře známou hodnotu hranice Chakrabarti a Khot [17] . $\Omega (n^{2})$ ${\tfrac {n^{2}}{4}}$ $\Omega (n))$ $\Omega (n\log ^{\tfrac {1}{12}}n)$ $\Omega (n^{\tfrac {5}{4)))$ $\Omega (n^{\tfrac {4}{3)))$ $\Omega (n^{\tfrac {4}{3}}\log ^{\tfrac {1}{3}}n)$

Některé nedávné výsledky dávají dolní meze, které jsou určeny kritickou pravděpodobností p monotónní vlastnosti daného grafu. Kritická pravděpodobnost p je definována jako jediné p takové, že náhodný graf G ( n , p ) má tuto vlastnost s pravděpodobností 1/2. Náhodný graf G ( n , p ) je graf s n vrcholy, ve kterém je každá hrana přítomna s pravděpodobností p a přítomnost/nepřítomnost hrany nezávisí na všech ostatních hranách. Friedgood, Kahn a Wigderson [18] ukázali, že jakýkoli monotónní graf invariantní s kritickou pravděpodobností p vyžaduje dotazy. U stejného problému vykázali O'Donnell, Sacks, Schramm a Servedio [19] spodní hranici na . $\Omega \left(\min \left\({\frac {n}{\min(p,1-p))),{\frac {n^{2)){\log n))\ dobře dobře)$ $\Omega ({\frac {n^{\tfrac {4}{3))}{p^{\tfrac {1}{3)))))$

Stejně jako v deterministickém případě existuje mnoho speciálních invariantů, pro které je známa dolní mez. Navíc jsou pro některé třídy grafových invariantů známy lepší meze. Například pro testování, zda má graf podgraf izomorfní k nějakému danému grafu (tzv. problém izomorfního podgrafu ), je podle Grögera nejznámější dolní mez [20] . $\Omega (n^{2})$ $\Omega (n^{\tfrac {3}{2)))$

Složitost kvantového dotazu

Pro jednotně ohraničenou chybu kvantové složitosti dotazu je nejznámější dolní mez , jak poznamenal Andrew Yao (výsledek není publikován, ale je zmíněn v [21] ). Hranice se získá kombinací pravděpodobnostní dolní mez s metodou kvantového protivníka . Nejlepší dolní mez, kterou lze dosáhnout , je na rozdíl od klasického případu díky Groverovu algoritmu , který poskytuje algoritmus s O( n ) dotazy pro testování monotónní vlastnosti neprázdnosti. Podobně jako v deterministických a pravděpodobnostních případech existují některé vlastnosti, o kterých je známo, že mají spodní mez , jako je neprázdnost (která vyplývá z optimality Groverova algoritmu) a vlastnost obsahovat trojúhelník . Je známo, že některé grafové invarianty mají spodní hranici a dokonce existují vlastnosti s dolní hranicí . Například vlastnost monotónní nerovinnosti vyžaduje dotazy [22] a monotónní vlastnost obsahovat více než polovinu možných hran (nazývaná také majoritní funkce) vyžaduje dotazy [23] . $\Omega (n^{\tfrac {2}{3}}\log ^{\tfrac {1}{6}}n)$ $\omega(n)$ $\omega(n)$ $\Omega (n^{\tfrac {3}{2)))$ $\Omega (n^{2})$ $\Theta (n{\tfrac {3}{2)))$ $\Theta (n^{2})$

Poznámky

↑ 1 2 Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ Tato definice odtoku se liší od obvyklé definice odtoku. Tato definice předpokládá, že všechny oblouky grafu vstupují do jednoho vrcholu (sink), zatímco obvyklá definice pouze předpokládá, že z propadu nejsou žádné vycházející oblouky (viz " Typy vrcholů grafu ").
↑ 1 2 Best, van Emde Boas, Lenstra, 1974 .
↑ Triesch, 1996 .
↑ Kleitman, Kwiatkowski, 1980 .
↑ 1 2 Kahn, Saks, Sturtevant, 1983 .
↑ Korneffel, Triesch, 2010 .
↑ Scheidweiler, Triesch, 2013 .
↑ Lutz, 2001 .
↑ Kozlov, 2008 , str. 226-228.
↑ Yao, 1988 .
↑ Chakrabarti, Khot, Shi, 2001 .
↑ Yao, 1991 .
↑ Král, 1988 .
↑ Hajnal, 1991 .
↑ Chakrabarti, Khot, 2001 .
↑ Friedgut, Kahn, Wigderson, 2002 .
↑ O'Donnell, Saks, Schramm, Servedio, 2005 .
↑ Gröger, 1992 .
↑ Magniez, Santha, Szegedy, 2005 .
↑ Ambainis, Iwama, Nakanishi, Nishimura a kol., 2008 .
↑ Beals, Buhrman, Cleve, Mosca, de Wolf, 2001 .

Literatura

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Složitost kvantových dotazů booleovských funkcí s malými on-sety // Proceedings of the 19th International Symposium on Algorithms and Computation. - Gold Coast, Austrálie: Springer-Verlag , 2008. - T. 5369. - S. 907-918. — (Poznámky z informatiky). - ISBN 978-3-540-92181-3 . - doi : 10.1007/978-3-540-92182-0_79 . .
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf. Kvantové dolní meze polynomů // Journal of the ACM . - 2001. - T. 48 , no. 4 . — S. 778–797 . - doi : 10.1145/502090.502097 . — arXiv : quant-ph/9802049 . .
Nejlepší MR, van Emde Boas P., Lenstra HW Přiostřená verze Aanderaa-Rosenbergovy domněnky. - Mathematisch Centrum Amsterdam , 1974. - (Zpráva ZW 30/74).
Amit Chakrabarti, Subhash Khot . Vylepšené spodní hranice náhodné složitosti vlastností grafu // Sborník příspěvků z 28. mezinárodního kolokvia o automatech, jazycích a programování. - Springer-Verlag, 2001. - T. 2076. - S. 285-296. — (Poznámky z informatiky). — ISBN 978-3-540-42287-7 . - doi : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot , Yaoyun Shi. Úhybnost zadržování podgrafů a související vlastnosti // SIAM Journal on Computing . - 2001. - T. 31 , no. 3 . — S. 866–875 . - doi : 10.1137/S0097539700382005 . .
Ehud Friedgut, Jeff Kahn, Avi Wigderson . Výpočet vlastností grafu pomocí náhodných oddílů podkrychle // Techniky náhodnosti a aproximace v informatice. - Springer-Verlag , 2002. - T. 2483. - S. 953. - (Poznámky k přednáškám z informatiky). — ISBN 978-3-540-44147-2 . - doi : 10.1007/3-540-45726-7_9 . .
Hans Dietmar Groger. O randomizované složitosti vlastností monotónního grafu // Acta Cybernetica. - 1992. - T. 10 , no. 3 . — S. 119–127 . Archivováno z originálu 24. září 2015. .
Petr Hajnal. Dolní mez Ω( n 4/3 ) pro randomizovanou složitost vlastností grafu // Combinatorica . - 1991. - T. 11 , no. 2 . — s. 131–143 . - doi : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. Topological approach to evasiveness // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium o základech informatiky . - Los Alamitos, CA, USA: IEEE Computer Society, 1983. - S. 31-33. - ISBN 0-8186-0508-1 . - doi : 10.1109/SFCS.1983.4 . .
Valerie Kingová. Dolní hranice složitosti vlastností grafu // Proc. 20. sympozium ACM o teorii výpočetní techniky . - Chicago, Illinois, Spojené státy americké, 1988. - str . 468-476 . — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Další výsledky Aanderaa-Rosenbergovy domněnky // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 . — S. 85–95 . - doi : 10.1016/0095-8956(80)90057-X .
Dmitrij Kozlov. Kombinatorická algebraická topologie. - Springer-Verlag, 2008. - ISBN 978-3-540-73051-4 .
Frank H. Lutz. Některé výsledky související s domněnkou vyhýbavosti // Journal of Combinatorial Theory, Series B. - 2001. - V. 81 , no. 1 . — S. 110–124 . - doi : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. Asymptotická mez pro složitost vlastností monotónního grafu // Combinatorica. - Springer-Verlag, 2010. - T. 30 , no. 6 . — S. 735–743 . — ISSN 0209-9683 . - doi : 10.1007/s00493-010-2485-3 .
Frederic Magniez, Miklos Santha, Mario Szegedy. Kvantové algoritmy pro problém trojúhelníku // Sborník příspěvků z šestnáctého výročního sympozia ACM-SIAM o diskrétních algoritmech . — Vancouver, British Columbia: Society for Industrial and Applied Mathematics , 2005. — s. 1109–1117. .
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Každý rozhodovací strom má vlivnou proměnnou // Proc 46. IEEE Symposium on Foundations of Computer Science . - 2005. - S. 31-39. — ISBN 0-7695-2468-0 . - doi : 10.1109/SFCS.2005.34 .
Ronald L. Rivest , Jean Vuillemin. Zobecnění a důkaz Aanderaa-Rosenbergovy domněnky // Proc. 7. sympozium ACM o teorii výpočetní techniky . - Albuquerque, Nové Mexiko, Spojené státy americké, 1975. - S. 6-11. - doi : 10.1145/800116.803747 . .
Arnold L. Rosenberg. Čas potřebný k rozpoznání vlastností grafů: problém // SIGACT News. - 1973. - V. 5 , čís. 4 . — S. 15–16 . - doi : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. Dolní hranice pro složitost vlastností monotónního grafu // SIAM Journal on Discrete Mathematics. - 2013. - T. 27 , č. 1 . — S. 257–265 . - doi : 10.1137/120888703 .
Eberhard Triesch. O rozpoznávací složitosti některých vlastností grafu // Combinatorica . - 1996. - T. 16 , no. 2 . — S. 259–268 . - doi : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Vlastnosti monotónního bipartitního grafu jsou vyhýbavé // SIAM Journal on Computing . - 1988. - T. 17 , no. 3 . — S. 517–520 . - doi : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Dolní hranice pro randomizované algoritmy pro vlastnosti grafu // Journal of Computer and System Sciences . - 1991. - T. 42 , no. 3 . — S. 267–287 . - doi : 10.1016/0022-0000(91)90003-N . .

Čtení pro další čtení

Béla Bollobas. Kapitola VIII. Složitost a balení // Extrémní teorie grafů. — New York: Dover Publications , 2004. — s. 401–437. - ISBN 978-0-486-43596-1 .
László Lovász & Young, Neal E., Poznámky k přednášce o úhybnosti vlastností grafu, arΧiv : cs/0205031v1 .
Catherine E Chronaki. Průzkum Evasiveness: Lower Bounds on the Decision Tree Complexity of Boolean Functions. — 1990.
Michael Sax. Rozhodovací stromy: Problémy a výsledky, staré a nové . Staženo 17. února 2019. Archivováno z originálu 3. března 2016. (neurčitý)