Aanderaa-Karp-Rosenberg-hypotesen

Uløste problemer med informatik : Bevis eller modbevis Aanderaa-Karp-Rosenberg-formodningen.

Aandera-Karp-Rosenberg- hypotesen (også kendt som Aandera-Rosenberg- hypotesen eller sværhedshypotesen ) er en gruppe af beslægtede hypoteser om antallet af spørgsmål i formen "Er der en kant mellem toppunkt u og toppunkt v ?" besvares for at afgøre, om en urettet graf har en bestemt egenskab (invariant), såsom at være plan eller todelt . Hypotesen er opkaldt efter den norske matematiker Stol Aanderaa og de amerikanske videnskabsmænd Richard M. Karp og Arnold L. Rosenberg. Ifølge hypotesen, for en bred klasse af invarianter, kan ingen algoritme garantere, at en algoritme kan udelade enhver forespørgsel - enhver algoritme til at bestemme, om en graf har en egenskab, uanset hvor smart denne algoritme er, skal kontrollere hvert par af hjørner før giver et svar. En egenskab, der opfylder hypotesen, kaldes hård .

Mere præcist siger Aandera-Rosenberg-formodningen, at enhver deterministisk algoritme skal teste mindst en fast brøkdel af alle mulige par af hjørnepunkter for i værste fald at bestemme ikke-triviel monoton egenskab ved grafen. I denne sammenhæng er en egenskab monoton, hvis den forbliver sand, når man tilføjer kanter (så planaritetsegenskaben er ikke monoton, men ikke-planaritetsegenskaben er monoton). En mere stringent version af denne formodning, kaldet sværhedshypotesen eller Aandera-Karp-Rosenberg-formodningen, siger, at netop testene er nødvendige. Versioner af problemet for probabilistiske og kvantealgoritmer blev formuleret og undersøgt. ${\tfrac {n(n-1)}{2))$

Den deterministiske Aanderaa-Rosenberg-formodning blev bevist af Rivest og Willemin [1] , men den stærkere Aanderaa-Karp-Rosenberg-formodning forbliver ubevist. Der er også en stor forskel mellem den nedre grænse og den bedst dokumenterede nedre grænse for sandsynlighed og kvantekompleksitet efter antal forespørgsler.

Eksempel

Egenskaben ved ikke at være tom (det vil sige at have mindst én kant) er monoton, da tilføjelse af endnu en kant til en ikke-tom graf producerer en ikke-tom graf. Der er en simpel algoritme til at teste om en graf ikke er tom - sløj gennem alle par af hjørner og kontroller om hvert par er forbundet med en kant. Findes en kant på denne måde, bryder vi løkken og rapporterer, at grafen ikke er tom, og hvis løkken slutter uden at finde nogen kant, så melder vi, at grafen er tom. På sådanne grafer (for eksempel komplette grafer ) afsluttes denne algoritme hurtigt uden at kontrollere hvert par af hjørner, men på en tom graf tjekker algoritmen alle mulige par, før den afsluttes. Derfor er kompleksiteten af algoritmen for forespørgsler ens - i værste fald foretager algoritmen checks. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Den ovenfor beskrevne algoritme er ikke den eneste mulige metode til at kontrollere for ikke-tomhed, men det følger af Aandera-Karp-Rosenberg-formodningen, at enhver determinant algoritme til at kontrollere for ikke-tomhed har samme forespørgselskompleksitet . Det vil sige, at egenskaben ved at være ikke-tom er vanskelig . For denne egenskab er resultatet nemt at kontrollere direkte - hvis algoritmen ikke udfører kontrol, vil den ikke være i stand til at skelne mellem en tom graf og en graf, der indeholder den ene kant af et umarkeret par hjørner og skal give et forkert svar for en af disse to grafer (enten for en tom eller for en graf med en kant ). ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Definitioner

I forbindelse med denne artikel vil alle grafer være enkle og urettede , medmindre andet er angivet. Det betyder, at kanterne på grafen danner et sæt (men ikke et multisæt ), og enderne af hver kant er et par adskilte hjørner. Grafer antages at have en implicit repræsentation , hvor hvert hjørne har en unik identifikator eller etiket, og hvor tilgrænsende to hjørner kan kontrolleres, men kun grundlæggende operationer kan udføres i tilstødende graf.

Uformelt er en grafegenskab (eller grafinvariant, begge udtryk bruges i flæng i denne artikel) en egenskab ved en graf, der er uafhængig af markup. Mere formelt er en grafegenskab en mapping fra sættet af alle grafer til {0,1}, således at isomorfe grafer afbildes til den samme værdi. For eksempel er egenskaben til at indeholde mindst ét toppunkt af grad 2 en grafinvariant, men egenskaben at det første toppunkt har grad 2 er ikke en grafinvariant, da egenskaben afhænger af grafens mærkning (især den afhænger af, hvilket toppunkt der betragtes som "det første"). En grafinvariant kaldes ikke-trivial, hvis den ikke har samme værdi for alle grafer. For eksempel er egenskaben ved at være en graf en triviel egenskab, da alle grafer har denne egenskab. Men på den anden side er egenskaben ved at være tom ikke-triviel, da en tom graf har denne egenskab, men en ikke-tom har ikke. En egenskab ved en graf siges at være monoton , hvis tilføjelse af kanter ikke ødelægger egenskaberne. Alternativt, hvis en graf har den monotone egenskab, så har enhver supergraf af den graf på det samme sæt af hjørner også denne egenskab. For eksempel er egenskaben ved at være ikke-plan monoton - supergrafen for en ikke-plan graf er også ikke-plan. Egenskaben ved at være regelmæssig er dog ikke monoton.

"O" -notationen bruges ofte til forespørgselskompleksitet . Kort fortalt er f ( n ) hvis for nogen stor nok til en positiv konstant c . Tilsvarende er f ( n ) hvis for stor nok til en positiv konstant c . Endelig er f ( n ) hvis det er både , og . $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))$

Anmodningskompleksitet

Kompleksiteten af en deterministisk forespørgsel til at evaluere en funktion på n bit er lig med antallet af bit x i , som den deterministiske algoritme skal læse i værste fald for at bestemme værdien af funktionen. For eksempel, hvis funktionen tager værdien 0, hvis alle bits er 0 og værdien 1 ellers (det vil sige OR- funktionen ), så er kompleksiteten af deterministiske forespørgsler nøjagtigt n . I værste fald vil de første n − 1 bit læst være 0, og værdien af funktionen vil kun afhænge af den sidste bit. Hvis algoritmen ikke læser denne bit, kan den give et forkert svar. Antallet af læste bit kaldes også antallet af anmodninger på inputtet. Man kan forestille sig, at algoritmen spørger (udfører en anmodning) et input om en bestemt bit, og inputtet reagerer på denne anmodning. $(x_{1},x_{2},\dots,x_{n})$

Kompleksiteten af en probabilistisk funktionsanmodning er defineret på samme måde, bortset fra at algoritmen kan være sandsynlighedsgrad, dvs. den kan kaste en mønt og bruge den rullede side af mønten til at bestemme, hvilken bit der skal anmodes om. Den probabilistiske algoritme skal dog fortsat give korrekte svar på alle inputforespørgsler - fejl er ikke tilladt. Sådanne algoritmer kaldes Las Vegas-algoritmer og bør skelnes fra Monte Carlo-algoritmer , hvor nogle fejl er tilladt. Kompleksiteten af en probabilistisk forespørgsel kan defineres i Monte Carlos forstand, men Aandera-Karp-Rosenberg-formodningen taler om kompleksiteten af forespørgsler for grafinvarianter i betydningen Las Vegas.

Kvantekompleksiteten af forespørgsler er en naturlig generalisering af kompleksiteten af en probabilistisk forespørgsel, naturligvis med opløsningen af kvanteforespørgsler og -svar. Kvanteforespørgselskompleksitet kan også defineres i form af Monte Carlo-algoritmer eller Las Vegas-algoritmer, men kvante-Monte Carlo-algoritmer menes normalt.

I sammenhæng med denne hypotese er den beregnede funktion en egenskab ved grafen, og inputtet er en streng af størrelse , som angiver placeringen af kanter på en graf med n hjørner, da en graf maksimalt kan have kanter. Kompleksiteten ved at anmode om en funktion er afgrænset ovenfra af værdien , da hele input vil blive læst efter anmodninger, hvilket bestemmer hele input grafen. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Kompleksiteten af deterministiske forespørgsler

For deterministiske algoritmer foreslog Rosenberg [2] , at for alle ikke-trivielle egenskaber af grafer på n toppunkter, kræver det forespørgsler at afgøre, om en graf har denne egenskab . Det er klart, at en ikke-triviel betingelse er påkrævet, da der er trivielle egenskaber som "er dette en graf?", der kan besvares uden nogen forespørgsel overhovedet. $\Omega (n^{2})$

Hypotesen blev tilbagevist af Aanderaa, som foreslog en egenskab ved en rettet graf (egenskaben ved at have en "sink"), hvis verifikation kun kræver O( n ) anmodninger. Et synk i en rettet graf er et toppunkt, der har in-grad n -1 og ud-grad 0 [3] . Denne egenskab kan tjekkes i mindre end 3n forespørgsler [4] . En egenskab ved en urettet graf, der kan verificeres i O( n )-forespørgsler, er egenskaben "graf er en skorpiongraf", først beskrevet i Best, van Emde Boas og Lenstra [4] . En skorpiongraf er en graf, der indeholder en sti, der består af tre spidser, således at stiens ene endepunkt er forbundet med alle de andre spidser på grafen, mens de to resterende spidser af stien kun er forbundet med spidserne på selve stien. .

Derefter formulerede Aanderaa og Rosenberg en ny formodning ( aanderaa-Rosenberg- hypotesen ), som siger, at det kræver forespørgsler [5] . Denne formodning blev løst af Raivest og Vuillemin [1] , hvilket viser, at der i det mindste er behov for forespørgsler for at teste enhver ikke-triviel monoton egenskab. Grænsen blev senere forbedret til Kleitman og Kwiatkowski [6] , derefter til Kahn, Sachs og Sturtevant [7] , til Kornefel og Trish [8] og til Scheiderweiler og 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 fremsatte en mere streng påstand (nu kaldet hårdhedsformodningen eller Aandera -Karp-Rosenberg-formodningen ), at "enhver ikke-triviel monoton egenskab ved grafer på n hjørner er svær" [10] . En egenskab siges at være svær , hvis det kræver forespørgsler [11] at afgøre, om grafen har den givne egenskab . Denne formodning siger, at den bedste algoritme til at teste enhver ikke-triviel monoton egenskab er at (i værste fald) forespørge alle mulige kanter. Denne formodning forbliver åben, selvom nogle specielle egenskaber ved grafer har vist sig at være vanskelige for alle n . Formodningen blev løst for det tilfælde, hvor n er en potens af et primtal af Kahn, Sacks og Sturtevant [7] ved hjælp af en topologisk tilgang. Formodningen blev løst for alle ikke-trivielle monotone egenskaber af todelte grafer af Yao [12] . Det har også vist sig, at mindre lukkede ejendomme også er vanskelige for store n [13] . ${\tfrac {n(n-1)}{2))$

Kompleksiteten af en sandsynlighedsforespørgsel

Richard Karp formodede også, at forespørgsler er påkrævet for at teste ikke-trivielle monotoniske egenskaber, selvom sandsynlighedsalgoritmer er tilladt. Der kendes ingen ikke-triviel egenskab, der kræver færre forespørgsler at kontrollere. En lineær nedre grænse (det vil sige for alle monotone egenskaber følger af en meget generel sammenhæng mellem probabilistiske og deterministiske forespørgselskompleksiteter . Den første superlineære nedre grænse for alle monotone invarianter blev givet af Yao [14] , som viste, at Der kræves forespørgsler. Det blev derefter forbedret af King [15 ] til , og derefter Hainal [16] til , Dette resultat blev derefter forbedret til den nuværende velkendte værdi af Chakrabarti og 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)$

Nogle nyere resultater giver lavere grænser, der bestemmes af den kritiske sandsynlighed p for den monotone egenskab for den pågældende graf. Den kritiske sandsynlighed p er defineret som den eneste p , således at den tilfældige graf G ( n , p ) har denne egenskab med sandsynlighed 1/2. En tilfældig graf G ( n , p ) er en graf med n toppunkter, hvor hver kant er til stede med sandsynlighed p og tilstedeværelsen/fraværet af en kant ikke afhænger af alle andre kanter. Friedgood, Kahn og Wigderson [18] viste, at enhver monoton grafinvariant med kritisk sandsynlighed p kræver forespørgsler. For det samme problem viste O'Donnell, Sacks, Schramm og Servedio [19] en nedre grænse på . $\Omega \left(\min \left\({\frac {n}{\min(p,1-p))),{\frac {n^{2)){\log n))\ højre\}\right)$ $\Omega ({\frac {n^{\tfrac {4}{3))}{p^{\tfrac {1}{3)))))$

Som i det deterministiske tilfælde er der mange specielle invarianter, for hvilke den nedre grænse er kendt. Desuden er bedre grænser kendt for nogle klasser af grafinvarianter. For for eksempel at teste om en graf har en subgraf, der er isomorf i forhold til en given graf (det såkaldte isomorfe subgrafproblem ), er den bedst kendte nedre grænse ifølge Gröger [20] . $\Omega (n^{2})$ $\Omega (n^{\tfrac {3}{2)))$

Kvanteforespørgselskompleksitet

For en ensartet afgrænset forespørgselskvantekompleksitetsfejl er den bedst kendte nedre grænse , som bemærket af Andrew Yao (resultatet er ikke offentliggjort, men er nævnt i [21] ). Bindningen opnås ved at kombinere en probabilistisk nedre grænse med en kvantemodstandsmetode . Den bedste nedre grænse, man håber at opnå, skyldes , i modsætning til det klassiske tilfælde, Grovers algoritme , som giver en algoritme med O( n )-forespørgsler til at teste for den monotone egenskab ved ikke-tomhed. I lighed med de deterministiske og probabilistiske tilfælde er der nogle egenskaber, der vides at have en nedre grænse , såsom ikke-tomhed (som følger af optimaliteten af Grovers algoritme) og egenskaben til at indeholde en trekant . Der er nogle grafinvarianter kendt for at have en nedre grænse , og der er endda egenskaber med en nedre grænse . For eksempel kræver den monotone ikke-planaritetsegenskab forespørgsler [22] , og den monotone egenskab til at indeholde mere end halvdelen af de mulige kanter (også kaldet majoritetsfunktionen) kræver forespørgsler [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})$

Noter

↑ 1 2 Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ Denne definition af afstrømning adskiller sig fra den sædvanlige definition af afstrømning. Denne definition forudsætter, at alle grafbuer kommer ind i et toppunkt (synk), mens den sædvanlige definition kun antager, at der ikke er nogen udgående buer fra synken (se " Typer af grafens toppunkter ").
↑ 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 , s. 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. Kvanteforespørgselskompleksitet af booleske funktioner med små on-sets // Proceedings of the 19th International Symposium on Algorithms and Computation. - Gold Coast, Australien: Springer-Verlag , 2008. - T. 5369. - P. 907-918. — (Forelæsningsnotater i datalogi). - 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. Nedre kvantegrænser ved polynomier // Journal of the ACM . - 2001. - T. 48 , no. 4 . — S. 778–797 . - doi : 10.1145/502090.502097 . — arXiv : quant-ph/9802049 . .
Best MR, van Emde Boas P., Lenstra HW En skærpet version af Aanderaa-Rosenberg-formodningen. - Mathematisch Centrum Amsterdam , 1974. - (Betænkning ZW 30/74).
Amit Chakrabarti, Subhash Khot . Forbedrede nedre grænser for den randomiserede kompleksitet af grafegenskaber // Proceedings of the 28th International Colloquium on Automata, Languages and Programming. - Springer-Verlag, 2001. - T. 2076. - S. 285-296. — (Forelæsningsnotater i datalogi). — ISBN 978-3-540-42287-7 . - doi : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot , Yaoyun Shi. Undgåelse af subgrafindeslutning og relaterede egenskaber // SIAM Journal on Computing . - 2001. - T. 31 , no. 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 randomiserede kompleksitet af monotone grafegenskaber // Acta Cybernetica. - 1992. - T. 10 , no. 3 . — S. 119–127 . Arkiveret fra originalen den 24. september 2015. .
Peter Hajnal. En Ω( n 4/3 ) nedre grænse for den randomiserede kompleksitet af grafegenskaber // Combinatorica . - 1991. - T. 11 , no. 2 . — s. 131–143 . - doi : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. En topologisk tilgang til undvigelse // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium om grundlaget for datalogi . - 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 for kompleksiteten af grafegenskaber // Proc. 20. ACM-symposium om teori om computing . - Chicago, Illinois, USA, 1988. - s . 468-476 . — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Yderligere resultater om Aanderaa-Rosenberg-formodningen // 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. Nogle resultater relateret til undvigelsesformodningen // Journal of Combinatorial Theory, Series B. - 2001. - V. 81 , no. 1 . — S. 110–124 . - doi : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. En asymptotisk bundet til kompleksiteten af monotone grafegenskaber // 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. Kvantealgoritmer til trekantsproblemet // Proceedings of the sekstende årlige ACM-SIAM symposium om diskrete algoritmer . - Vancouver, British Columbia: Society for Industrial and Applied Mathematics , 2005. - s. 1109-1117. .
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Hvert beslutningstræ har en indflydelsesrig 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 og bevis på Aanderaa-Rosenberg-formodningen // Proc. 7. ACM-symposium om databehandlingsteori . - Albuquerque, New Mexico, USA, 1975. - S. 6-11. - doi : 10.1145/800116.803747 . .
Arnold L. Rosenberg. Om den tid, der kræves for at genkende egenskaber ved grafer: et problem // SIGACT News. - 1973. - V. 5 , no. 4 . — S. 15–16 . - doi : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. En nedre grænse for kompleksiteten af monotone grafegenskaber // SIAM Journal om diskret matematik. - 2013. - T. 27 , nr. 1 . — S. 257–265 . - doi : 10.1137/120888703 .
Eberhard Triesch. Om genkendelseskompleksiteten af nogle grafegenskaber // Combinatorica . - 1996. - T. 16 , no. 2 . — S. 259–268 . - doi : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Monotone bipartite grafegenskaber er undvigende // SIAM Journal on Computing . - 1988. - T. 17 , no. 3 . — S. 517–520 . - doi : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Nedre grænser for randomiserede algoritmer for grafegenskaber // Journal of Computer and System Sciences . - 1991. - T. 42 , no. 3 . — S. 267–287 . - doi : 10.1016/0022-0000(91)90003-N . .

Læsning for yderligere læsning

Bela Bollobas. Kapitel VIII. Kompleksitet og pakning // 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øgelse af undvigelsesevne: Nedre grænser for beslutningstræets kompleksitet af booleske funktioner. - 1990.
Michael Sax. Beslutningstræer: Problemer og resultater, gamle og nye . Hentet 17. februar 2019. Arkiveret fra originalen 3. marts 2016. (ubestemt)