Aanderaa-Karp-Rosenberg-hypotesen

Olösta problem med informatik : Bevisa eller motbevisa Aanderaa-Karp-Rosenbergs gissning.

Aandera-Karp-Rosenberg- hypotesen (även känd som Aandera-Rosenberg- hypotesen eller svårighetshypotesen ) är en grupp relaterade hypoteser om antalet frågor i formen "Finns det en kant mellan vertex u och vertex v ?" besvaras för att avgöra om en oriktad graf har en viss egenskap (invariant), som att vara plan eller bipartit . Hypotesen är uppkallad efter den norske matematikern Stol Aanderaa och de amerikanska vetenskapsmännen Richard M. Karpoch Arnold L. Rosenberg. Enligt hypotesen, för en bred klass av invarianter, kan ingen algoritm garantera att en algoritm kan utelämna någon fråga - vilken algoritm som helst för att avgöra om en graf har en egenskap, oavsett hur smart denna algoritm är, måste kontrollera varje par av hörn innan ger ett svar. En egenskap som uppfyller hypotesen kallas hard .

Mer exakt säger Aandera-Rosenbergs gissning att varje deterministisk algoritm måste testa åtminstone en fast bråkdel av alla möjliga hörnpar för att i värsta fall bestämma icke-triviala monotona egenskap. I detta sammanhang är en egenskap monoton om den förblir sann när man lägger till kanter (så planaritetsegenskapen är inte monoton, men icke-planaritetsegenskapen är monoton). En mer rigorös version av denna gissning, kallad svårighetshypotesen eller Aandera-Karp-Rosenbergs gissning, säger att exakt testerna behövs. Versioner av problemet för probabilistiska och kvantalgoritmer formulerades och studerades. ${\tfrac {n(n-1)}{2))$

Den deterministiska Aanderaa-Rosenberg-förmodan bevisades av Rivest och Willemin [1] , men den starkare Aanderaa-Karp-Rosenberg-förmodan förblir obevisad. Det finns också en stor skillnad mellan den nedre gränsen och den bäst beprövade nedre gränsen för probabilistisk och kvantkomplexitet efter antal frågor.

Exempel

Egenskapen att inte vara tom (det vill säga att ha minst en kant) är monoton, eftersom att lägga till ytterligare en kant till en icke-tom graf ger en icke-tom graf. Det finns en enkel algoritm för att testa om en graf inte är tom - gå igenom alla par av hörn och kontrollera om varje par är sammankopplade med en kant. Om en kant hittas på detta sätt bryter vi slingan och rapporterar att grafen inte är tom, och om slingan slutar utan att hitta någon kant, då rapporterar vi att grafen är tom. På sådana grafer (till exempel kompletta grafer ) avslutas denna algoritm snabbt utan att kontrollera varje par av hörn, men på en tom graf kontrollerar algoritmen alla möjliga par innan den avslutas. Därför är komplexiteten i algoritmen för frågor lika - i värsta fall gör algoritmen kontroller. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Algoritmen som beskrivs ovan är inte den enda möjliga metoden för att kontrollera om den inte är tom, men det följer av Aandera-Karp-Rosenbergs gissning att alla determinanta algoritmerna för att kontrollera om de inte är tomma har samma frågekomplexitet . Det vill säga att egenskapen att vara icke-tom är svår . För den här egenskapen är resultatet lätt att kontrollera direkt - om algoritmen inte utför kontroller kommer den inte att kunna skilja mellan en tom graf och en graf som innehåller en kant av ett omarkerat par av hörn och måste ge ett felaktigt svar för en av dessa två grafer (antingen för en tom eller för en graf med kant ). ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Definitioner

För syftet med denna artikel kommer alla grafer att vara enkla och oriktade , om inte annat anges. Detta betyder att kanterna på grafen bildar en uppsättning (men inte en multiset ) och att ändarna på varje kant är ett par distinkta hörn. Grafer antas ha en implicit representation där varje vertex har en unik identifierare eller etikett och där närliggande två hörn kan kontrolleras, men endast grundläggande operationer kan utföras i närliggande graf.

Informellt sett är en grafegenskap (eller grafinvariant, båda termerna används omväxlande i den här artikeln) en egenskap hos en graf som är oberoende av uppmärkning. Mer formellt är en grafegenskap en mappning från uppsättningen av alla grafer till {0,1} så att isomorfa grafer mappas till samma värde. Till exempel är egenskapen att innehålla minst en vertex av grad 2 en grafinvariant, men egenskapen att den första vertexen har grad 2 är inte en grafinvariant, eftersom egenskapen beror på grafens märkning (i synnerhet den beror på vilken vertex som anses vara "den första"). En grafinvariant kallas icke-trivial om den inte har samma värde för alla grafer. Till exempel är egenskapen att vara en graf en trivial egenskap, eftersom alla grafer har denna egenskap. Men å andra sidan är egenskapen att vara tom icke-trivial, eftersom en tom graf har denna egenskap, men en icke-tom inte. En egenskap hos en graf sägs vara monoton om att lägga till kanter inte förstör egenskaperna. Alternativt, om en graf har den monotona egenskapen, så har varje supergraf av den grafen på samma uppsättning hörn också denna egenskap. Till exempel, egenskapen att vara icke-plan är monoton - supergrafen för en icke-plan graf är också icke-plan. Egenskapen att vara regelbunden är dock inte monoton.

"O" -notationen används ofta för frågekomplexitet . Kortfattat är f ( n ) om för någon stor nog för någon positiv konstant c . På liknande sätt är f ( n ) om för stor nog för någon positiv konstant c . Slutligen är f ( n ) om det är både , och . $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))$

Begärans komplexitet

Komplexiteten hos en deterministisk fråga för att utvärdera en funktion med n bitar är lika med antalet bitar x i som den deterministiska algoritmen måste läsa i värsta fall för att bestämma värdet på funktionen. Till exempel, om funktionen tar värdet 0 om alla bitar är 0 och värdet 1 annars (det vill säga ELLER- funktionen ), då är komplexiteten för deterministiska frågor exakt n . I värsta fall blir de första n − 1 bitarna avlästa 0 och värdet på funktionen beror endast på den sista biten. Om algoritmen inte läser denna bit kan den ge ett felaktigt svar. Antalet lästa bitar kallas också antalet förfrågningar som görs på ingången. Man kan föreställa sig att algoritmen frågar (utför en begäran) en inmatning om en viss bit och ingången svarar på denna begäran. $(x_{1},x_{2},\dots,x_{n})$

Komplexiteten hos en probabilistisk funktionsbegäran definieras på liknande sätt, förutom att algoritmen kan vara probabilistisk, det vill säga den kan kasta ett mynt och använda den rullade sidan av myntet för att bestämma vilken bit som ska begäras. Den probabilistiska algoritmen måste dock fortsätta att ge korrekta svar på alla inmatningsförfrågningar - fel är inte tillåtna. Sådana algoritmer kallas Las Vegas-algoritmer och bör särskiljas från Monte Carlo-algoritmer , där vissa fel är tillåtna. Komplexiteten hos en probabilistisk fråga kan definieras i betydelsen Monte Carlo, men Aandera-Karp-Rosenbergs gissning talar om komplexiteten hos frågor för grafinvarianter i betydelsen Las Vegas.

Kvantkomplexiteten för frågor är en naturlig generalisering av komplexiteten hos en probabilistisk fråga, naturligtvis med upplösningen av kvantfrågor och svar. Kvantfrågekomplexitet kan också definieras i termer av Monte Carlo-algoritmer eller Las Vegas-algoritmer, men kvant-Monte Carlo-algoritmer avses vanligtvis.

I samband med denna hypotes är den beräknade funktionen en egenskap hos grafen, och inmatningen är en sträng av storlek , som specificerar placeringen av kanter på en graf med n hörn, eftersom en graf kan ha maximalt med kanter. Komplexiteten i att begära en funktion begränsas ovanifrån av värdet eftersom hela inmatningen läses efter förfrågningar, vilket bestämmer hela inmatningsgrafen. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Komplexiteten hos deterministiska frågor

För deterministiska algoritmer föreslog Rosenberg [2] att för alla icke-triviala egenskaper hos grafer på n hörn, krävs frågor för att avgöra om en graf har denna egenskap . Det är tydligt att ett icke-trivialt villkor krävs, eftersom det finns triviala egenskaper som "är det här en graf?" som kan besvaras utan någon fråga alls. $\Omega (n^{2})$

Hypotesen tillbakavisades av Aanderaa, som föreslog en egenskap hos en riktad graf (egenskapen att ha en "sink"), vars verifiering endast kräver O( n )-förfrågningar. En sänka i en riktad graf är en vertex som har in-grad n -1 och ut-grad 0 [3] . Den här egenskapen kan kontrolleras i mindre än 3n frågor [4] . En egenskap hos en oriktad graf som kan verifieras i O( n )-frågor är egenskapen "graf är en skorpiongraf", som först beskrivs i Best, van Emde Boas och Lenstra [4] . En skorpiongraf är en graf som innehåller en bana som består av tre hörn så att banans ena ändpunkt är ansluten till alla andra hörn av grafen, medan de två återstående hörn av banan är anslutna endast till själva höjdpunkterna på banan. .

Sedan formulerade Aanderaa och Rosenberg en ny gissning ( Aderaa-Rosenberg- hypotesen ), som säger att det krävs frågor [5] . Denna gissning löstes av Raivest och Vuillemin [1] , vilket visar att åtminstone frågor behövs för att testa alla icke-triviala monotona egenskaper. Gränsen förbättrades senare till Kleitman och Kwiatkowski [6] , sedan till Kahn, Sachs och Sturtevant [7] , till Kornefel och Trish [8] och till Scheiderweiler och 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 gjorde ett mer rigoröst påstående (nu kallad hårdhetsförmodan eller Aandera -Karp-Rosenberg-förmodan ) att "alla icke-triviala monotona egenskaper hos grafer på n hörn är svåra" [10] . En egenskap sägs vara svår om det krävs frågor [11] för att avgöra om grafen har den givna egenskapen . Denna gissning säger att den bästa algoritmen för att testa alla icke-triviala monotona egenskaper är att (i värsta fall) fråga alla möjliga kanter. Denna gissning förblir öppen, även om vissa speciella egenskaper hos grafer har visat sig vara svåra för alla n . Gissningen löstes för fallet när n är en potens av ett primtal av Kahn, Sacks och Sturtevant [7] med ett topologiskt tillvägagångssätt. Gissningen löstes för alla icke-triviala monotona egenskaper hos tvådelade grafer av Yao [12] . Det har också visat sig att mindre stängda fastigheter också är svåra för stora n [13] . ${\tfrac {n(n-1)}{2))$

En probabilistisk frågas komplexitet

Richard Karp antog också att frågor krävs för att testa icke-triviala monotoniska egenskaper, även om probabilistiska algoritmer är tillåtna. Ingen icke-trivial egenskap är känd som kräver färre frågor att kontrollera. En linjär nedre gräns (det vill säga för alla monotona egenskaper följer av ett mycket allmänt samband mellan probabilistisk och deterministisk frågekomplexitet . Den första superlinjära nedre gränsen för alla monotona invarianter gavs av Yao [14] , som visade att Förfrågningar krävs. Det förbättrades sedan av King [15 ] till , och sedan Hainal [16] till , Detta resultat förbättrades sedan till det nuvarande välkända värdet av Chakrabarti- och Khot -gränsen [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)$

Vissa nya resultat ger lägre gränser som bestäms av den kritiska sannolikheten p för den monotona egenskapen hos grafen i fråga. Den kritiska sannolikheten p definieras som den enda p så att den slumpmässiga grafen G ( n , p ) har denna egenskap med sannolikheten 1/2. En slumpmässig graf G ( n , p ) är en graf med n hörn där varje kant är närvarande med sannolikhet p och närvaron/frånvaron av en kant inte beror på alla andra kanter. Friedgood, Kahn och Wigderson [18] visade att varje monoton grafinvariant med kritisk sannolikhet p kräver frågor. För samma problem visade O'Donnell, Sacks, Schramm och Servedio [19] en nedre gräns på . $\Omega \left(\min \left\({\frac {n}{\min(p,1-p))),{\frac {n^{2)){\log n))\ visst visst)$ $\Omega ({\frac {n^{\tfrac {4}{3))}{p^{\tfrac {1}{3)))))$

Liksom i det deterministiska fallet finns det många speciella invarianter för vilka den nedre gränsen är känd. Dessutom är bättre gränser kända för vissa klasser av grafinvarianter. Till exempel, för att testa om en graf har en subgraf som är isomorf till någon given graf (det så kallade isomorfa subgrafproblemet ), är den mest kända nedre gränsen, enligt Gröger, [20] . $\Omega (n^{2})$ $\Omega (n^{\tfrac {3}{2)))$

Quantum query komplexitet

För ett enhetligt begränsat frågekvantkomplexitetsfel är den mest kända nedre gränsen , som noterats av Andrew Yao (resultatet publiceras inte, men nämns i [21] ). Bindningen erhålls genom att kombinera en probabilistisk nedre gräns med en kvantmotståndsmetod . Den bästa nedre gränsen man hoppas uppnå är , i motsats till det klassiska fallet, på grund av Grovers algoritm , som tillhandahåller en algoritm med O( n )-frågor för att testa för den monotona egenskapen nonemptiness. I likhet med deterministiska och probabilistiska fallen, finns det vissa egenskaper som är kända för att ha en lägre gräns , till exempel nonemptiness (vilket följer av optimaliteten hos Grovers algoritm) och egenskapen att innehålla en triangel . Det finns några grafinvarianter som är kända för att ha en nedre gräns , och det finns även egenskaper med en lägre gräns . Till exempel kräver den monotona icke-planaritetsegenskapen frågor [22] , och den monotona egenskapen för att innehålla mer än hälften av de möjliga kanterna (även kallad majoritetsfunktionen) kräver frågor [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})$

Anteckningar

↑ 1 2 Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ Denna definition av avrinning skiljer sig från den vanliga definitionen av avrinning. Den här definitionen förutsätter att alla grafbågar går in i ett hörn (sänka), medan den vanliga definitionen endast antar att det inte finns några utgående bågar från sänkan (se " Typer av grafhörn ").
↑ 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 , sid. 226-228.
↑ Yao, 1988 .
↑ Chakrabarti, Khot, Shi, 2001 .
↑ Yao, 1991 .
↑ King, 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 et al., 2008 .
↑ Beals, Buhrman, Cleve, Mosca, de Wolf, 2001 .

Litteratur

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Kvantfrågekomplexitet för booleska funktioner med små on-set // Proceedings of the 19th International Symposium on Algorithms and Computation. - Gold Coast, Australien: Springer-Verlag , 2008. - T. 5369. - P. 907-918. — (Föreläsningsanteckningar i datavetenskap). - 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. Quantum nedre gränser av polynom // Journal of the ACM . - 2001. - T. 48 , nr. 4 . — S. 778–797 . - doi : 10.1145/502090.502097 . — arXiv : quant-ph/9802049 . .
Best MR, van Emde Boas P., Lenstra HW En skärpt version av Aanderaa-Rosenberg-förmodan. - Mathematisch Centrum Amsterdam , 1974. - (Rapport ZW 30/74).
Amit Chakrabarti, Subhash Khot . Förbättrade nedre gränser för den randomiserade komplexiteten av grafegenskaper // Proceedings of the 28th International Colloquium on Automata, Languages and Programming. - Springer-Verlag, 2001. - T. 2076. - S. 285-296. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-540-42287-7 . - doi : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot , Yaoyun Shi. Undvikande av subgrafinneslutning och relaterade egenskaper // SIAM Journal on Computing . - 2001. - T. 31 , nr. 3 . — S. 866–875 . - doi : 10.1137/S0097539700382005 . .
Ehud Friedgut, Jeff Kahn, Avi Wigderson . Computing Graph Properties by Randomized Subcube Partitions // Randomization and Approximation Techniques in Computer Science. - Springer-Verlag , 2002. - T. 2483. - S. 953. - (Lecture Notes in Computer Science). — ISBN 978-3-540-44147-2 . - doi : 10.1007/3-540-45726-7_9 . .
Hans Dietmar Groger. Om den randomiserade komplexiteten hos monotona grafegenskaper // Acta Cybernetica. - 1992. - T. 10 , nr. 3 . — S. 119–127 . Arkiverad från originalet den 24 september 2015. .
Peter Hajnal. En Ω( n 4/3 ) nedre gräns för den randomiserade komplexiteten av grafegenskaper // Combinatorica . - 1991. - T. 11 , nr. 2 . — s. 131–143 . - doi : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. A topological approach to evasiveness // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium om grunderna för datavetenskap . - Los Alamitos, CA, USA: IEEE Computer Society, 1983. - S. 31–33. - ISBN 0-8186-0508-1 . - doi : 10.1109/SFCS.1983.4 . .
Valerie King. Nedre gränser för komplexiteten hos grafegenskaper // Proc. 20:e ACM Symposium on Theory of Computing . - Chicago, Illinois, USA, 1988. - s . 468-476 . — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Ytterligare resultat om Aanderaa-Rosenberg-förmodan // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 . — S. 85–95 . - doi : 10.1016/0095-8956(80)90057-X .
Dmitry Kozlov. Kombinatorisk algebraisk topologi. - Springer-Verlag, 2008. - ISBN 978-3-540-73051-4 .
Frank H. Lutz. Några resultat relaterade till undvikandeförmodan // Journal of Combinatorial Theory, Series B. - 2001. - V. 81 , nr. 1 . — S. 110–124 . - doi : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. En asymptotisk bunden för komplexiteten hos monotona grafegenskaper // Combinatorica. - Springer-Verlag, 2010. - T. 30 , nr. 6 . — S. 735–743 . — ISSN 0209-9683 . - doi : 10.1007/s00493-010-2485-3 .
Frederic Magniez, Miklos Santha, Mario Szegedy. Kvantalgoritmer för triangelproblemet // Proceedings of the sextonth annual ACM-SIAM symposium on Discrete algorithms . — Vancouver, British Columbia: Society for Industrial and Applied Mathematics , 2005. — s. 1109–1117. .
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Varje beslutsträd har en inflytelserik variabel // Proc 46th 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. En generalisering och bevis på Aanderaa-Rosenbergs gissning // Proc. 7:e ACM-symposiet om datorteori . - Albuquerque, New Mexico, USA, 1975. - S. 6-11. - doi : 10.1145/800116.803747 . .
Arnold L. Rosenberg. Om tiden som krävs för att känna igen egenskaperna hos grafer: ett problem // SIGACT News. - 1973. - V. 5 , nr. 4 . — S. 15–16 . - doi : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. En nedre gräns för komplexiteten hos monotona grafegenskaper // SIAM Journal on Discrete Mathematics. - 2013. - T. 27 , nr 1 . — S. 257–265 . - doi : 10.1137/120888703 .
Eberhard Triesch. Om igenkänningskomplexiteten hos vissa grafegenskaper // Combinatorica . - 1996. - T. 16 , nr. 2 . — S. 259–268 . - doi : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Monotona bipartite grafegenskaper är undvikande // SIAM Journal on Computing . - 1988. - T. 17 , nr. 3 . — S. 517–520 . - doi : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Nedre gränser för randomiserade algoritmer för grafegenskaper // Journal of Computer and System Sciences . - 1991. - T. 42 , nr. 3 . — S. 267–287 . - doi : 10.1016/0022-0000(91)90003-N . .

Läsning för vidare läsning

Bela Bollobas. Kapitel VIII. Komplexitet och packning // Extreme Graph Theory. — New York: Dover Publications , 2004. — s. 401–437. - ISBN 978-0-486-43596-1 .
László Lovász & Young, Neal E., Lecture Notes on Evasiveness of Graph Properties, arΧiv : cs/0205031v1 .
Catherine E Chronaki. En undersökning av undvikande: Nedre gränser för beslutsträdets komplexitet för booleska funktioner. — 1990.
Michael Sax. Beslutsträd: problem och resultat, gamla och nya . Hämtad 17 februari 2019. Arkiverad från originalet 3 mars 2016. (obestämd)