Aanderaa-Karp-Rosenbergin hypoteesi

Ratkaisemattomat informatiikan ongelmat : Todista tai kumoa Aanderaa-Karp-Rosenberg-oletus.

Aandera-Karp-Rosenberg- hypoteesi (tunnetaan myös nimellä Aandera-Rosenberg- hypoteesi tai vaikeushypoteesi ) on joukko toisiinsa liittyviä hypoteeseja , jotka koskevat kysymysten määrää muodossa "Onko kärjen u ja kärjen v välillä reuna ?" vastataan määrittääksesi, onko suuntaamattomalla graafilla tietty ominaisuus (invariantti), kuten taso tai kaksiosainen . Hypoteesi on nimetty norjalaisen matemaatikon Stol Aanderaan sekä amerikkalaisten tiedemiesten Richard M. Karpin ja Arnold L. Rosenbergin mukaan. Hypoteesin mukaan laajalle invarianttien luokalle mikään algoritmi ei voi taata, että algoritmi voi jättää pois minkä tahansa kyselyn - minkä tahansa algoritmin, jolla määritetään, onko graafilla ominaisuus, riippumatta siitä, kuinka älykäs tämä algoritmi on, on tarkistettava jokainen pistepari ennen antaa vastauksen. Ominaisuutta, joka täyttää hypoteesin, kutsutaan kovaksi .

Tarkemmin sanottuna Aandera-Rosenbergin arvelussa sanotaan, että minkä tahansa deterministisen algoritmin on testattava vähintään kiinteä osa kaikista mahdollisista kärkipareista määrittääkseen pahimmassa tapauksessa graafin ei-triviaalin monotonisen ominaisuuden. Tässä yhteydessä ominaisuus on monotoninen, jos se pysyy tosi, kun lisätään reunoja (siis tasomaisuusominaisuus ei ole monotoninen, mutta ei-tasoisuusominaisuus on monotoninen). Tämän olettamuksen tiukempi versio, jota kutsutaan vaikeushypoteesiksi tai Aandera-Karp-Rosenbergin olettamukseksi, sanoo, että juuri testejä tarvitaan. Tehtävästä laadittiin ja tutkittiin versioita todennäköisyys- ja kvanttialgoritmeille . ${\tfrac {n(n-1)}{2))$

Rivest ja Willemin [1] osoittivat deterministisen Aanderaa-Rosenberg-oletuksen , mutta vahvempi Aanderaa-Karp-Rosenberg-oletus on edelleen todistamatta. Lisäksi todennäköisyys- ja kvanttimonimutkaisuuden alarajan ja parhaiten todistetun alarajan välillä on suuri ero kyselyiden lukumäärän perusteella.

Esimerkki

Ominaisuus olla tyhjä (eli sillä on vähintään yksi reuna) on monotoninen, koska toisen reunan lisääminen ei-tyhjään graafiin tuottaa ei-tyhjän graafin. On olemassa yksinkertainen algoritmi, jolla testataan, onko graafi ei-tyhjä - käy läpi kaikki pisteparit ja tarkista, onko jokainen pari yhdistetty reunalla. Jos reuna löytyy tällä tavalla, katkaisemme silmukan ja raportoimme, että graafi ei ole tyhjä, ja jos silmukka päättyy löytämättä yhtään reunaa, raportoimme graafin olevan tyhjä. Tällaisissa kaavioissa (esimerkiksi täydelliset graafit ) tämä algoritmi päättyy nopeasti tarkistamatta jokaista pisteparia, mutta tyhjässä graafissa algoritmi tarkistaa kaikki mahdolliset parit ennen lopettamista. Siksi kyselyiden algoritmin monimutkaisuus on yhtä suuri - pahimmassa tapauksessa algoritmi tekee tarkistuksia. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Yllä kuvattu algoritmi ei ole ainoa mahdollinen menetelmä epätyhjyyden tarkistamiseen, mutta Aandera-Karp-Rosenberg-oletuksesta seuraa, että millä tahansa determinanttisella algoritmilla ei-tyhjyyden tarkistamiseksi on sama kyselyn monimutkaisuus . Eli ominaisuus olla ei-tyhjä on vaikea . Tämän ominaisuuden osalta tulos on helppo tarkistaa suoraan - jos algoritmi ei suorita tarkistuksia, se ei pysty erottamaan tyhjää graafia ja graafia, joka sisältää tarkastamattoman pisteparin yhden reunan, ja sen on annettava virheellinen vastaus toinen näistä kahdesta graafista (joko tyhjälle tai graafille, jonka reuna on ). ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Määritelmät

Tässä artikkelissa kaikki kaaviot ovat yksinkertaisia ja suuntaamattomia , ellei toisin mainita. Tämä tarkoittaa, että graafin reunat muodostavat joukon (mutta ei multisarjaa ) ja kunkin reunan päät ovat pari erillisiä pisteitä. Graafilla oletetaan olevan implisiittinen esitys , jossa jokaisella kärjellä on yksilöllinen tunniste tai otsikko ja jossa kahden kärjen viereisyys voidaan tarkistaa, mutta viereisyysgraafissa voidaan suorittaa vain perusoperaatioita.

Epämuodollisesti graafin ominaisuus (tai graafin invariantti, molempia termejä käytetään tässä artikkelissa vaihtokelpoisesti) on graafin ominaisuus, joka on riippumaton merkinnöistä. Muodollisemmin graafin ominaisuus on kuvaus kaikkien kaavioiden joukosta arvoon {0,1} siten, että isomorfiset kaaviot kartoitetaan samaan arvoon. Esimerkiksi ominaisuus sisältää ainakin yhden asteen 2 kärjen on graafin invariantti, mutta ominaisuus, että ensimmäisellä kärjellä on aste 2, ei ole graafiinvariantti, koska ominaisuus riippuu graafin merkinnästä (erityisesti siitä riippuu siitä, mitä kärkeä pidetään "ensimmäisenä"). Kuvaajan invarianttia kutsutaan ei-triviaaliksi, jos sillä ei ole samaa arvoa kaikille kaavioille. Esimerkiksi ominaisuus olla graafi on triviaali ominaisuus, koska kaikilla kaavioilla on tämä ominaisuus. Mutta toisaalta ominaisuus olla tyhjä on ei-triviaali, koska tyhjällä graafilla on tämä ominaisuus, mutta ei-tyhjällä ei. Graafin ominaisuuden sanotaan olevan monotoninen , jos reunojen lisääminen ei tuhoa ominaisuuksia. Vaihtoehtoisesti, jos graafilla on monotoninen ominaisuus, niin minkä tahansa graafin supergraafilla samassa pistejoukossa on myös tämä ominaisuus. Esimerkiksi ominaisuus olla epätasoinen on monotoninen – ei-tasoisen graafin supergraafi on myös ei-tasoinen. Säännöllisyyden ominaisuus ei kuitenkaan ole yksitoikkoinen.

"O" -merkintää käytetään usein kyselyn monimutkaisuuteen . Lyhyesti sanottuna f ( n ) on jos mille tahansa tarpeeksi suurelle jollekin positiiviselle vakiolle c . Vastaavasti f ( n ) on riittävän suuri jollekin positiiviselle vakiolle c . Lopuksi f ( n ) on , jos se on sekä , että . $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))$

Pyynnön monimutkaisuus

Deterministisen kyselyn monimutkaisuus n bitin funktion arvioimiseksi on yhtä suuri kuin bittien lukumäärä x i , joka deterministisen algoritmin on luettava pahimmassa tapauksessa määrittääkseen funktion arvon. Esimerkiksi jos funktio saa arvon 0, jos kaikki bitit ovat 0 ja arvon 1 muuten (eli TAI -funktio ), niin determinististen kyselyiden monimutkaisuus on täsmälleen n . Pahimmassa tapauksessa ensimmäiset n − 1 luettua bittiä ovat 0 ja funktion arvo riippuu vain viimeisestä bitistä. Jos algoritmi ei lue tätä bittiä, se voi antaa väärän vastauksen. Luettujen bittien määrää kutsutaan myös tuloon tehtyjen pyyntöjen lukumääräksi. Voidaan kuvitella, että algoritmi kysyy (suorittaa pyynnön) syötteen tietystä bitistä ja tulo vastaa tähän pyyntöön. $(x_{1},x_{2},\pisteet ,x_{n})$

Todennäköisyysfunktiopyynnön monimutkaisuus määritellään samalla tavalla, paitsi että algoritmi voi olla todennäköisyyspohjainen, eli se voi heittää kolikon ja käyttää kolikon rullattua puolta päättääkseen, mitä bittiä pyytää. Todennäköisyyspohjaisen algoritmin on kuitenkin edelleen annettava oikeat vastaukset kaikkiin syöttöpyyntöihin - virheet eivät ole sallittuja. Tällaisia algoritmeja kutsutaan Las Vegasin algoritmeiksi, ja ne tulisi erottaa Monte Carlo -algoritmeista , joissa jotkin virheet ovat sallittuja. Todennäköisyyspohjaisen kyselyn monimutkaisuus voidaan määritellä Monte Carlon merkityksessä, mutta Aandera-Karp-Rosenbergin olettamus puhuu graafin invarianttien kyselyiden monimutkaisuudesta Las Vegasin merkityksessä.

Kyselyjen kvanttimonimutkaisuus on luonnollinen yleistys todennäköisyyspohjaisen kyselyn monimutkaisuudesta, luonnollisesti kvanttikyselyjen ja -vastausten ratkaisulla. Kvanttikyselyn monimutkaisuus voidaan määritellä myös Monte Carlo -algoritmeilla tai Las Vegas -algoritmeilla, mutta yleensä tarkoitetaan kvantti-Monte Carlo -algoritmeja.

Tämän hypoteesin yhteydessä laskettu funktio on graafin ominaisuus ja syöte on merkkijono koko , joka määrittää reunojen sijainnin graafissa, jossa on n kärkeä, koska graafissa voi olla korkeintaan särmiä. Minkä tahansa funktion pyytämisen monimutkaisuus on ylhäältä päin rajattu arvolla , koska koko syöte luetaan pyyntöjen jälkeen, mikä määrittää koko syötekaavion. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Determinististen kyselyiden monimutkaisuus

Deterministisille algoritmeille Rosenberg [2] ehdotti, että kaikkien n - pisteen graafien ei-triviaalisten ominaisuuksien osalta sen päättäminen, onko graafilla tämä ominaisuus, vaatii kyselyjä. On selvää, että ei-triviaaliehto vaaditaan, koska on olemassa triviaaleja ominaisuuksia, kuten "onko tämä graafi?", joihin voidaan vastata ilman kyselyä. $\Omega (n^{2})$

Hypoteesin kumosi Aanderaa, joka ehdotti suunnatun graafin ominaisuutta (ominaisuuden olla "nielu"), jonka todentaminen vaatii vain O( n ) pyyntöä. Suunnatun graafin nielu on kärki, jolla on sisä-aste n -1 ja ulkoaste 0 [3] . Tämä ominaisuus voidaan tarkistaa alle 3n kyselyssä [4] . Suuntaamattoman graafin ominaisuus, joka voidaan todentaa O( n )-kyselyissä, on "graafi on skorpionigraafi" -ominaisuus, joka on kuvattu ensimmäisen kerran teoksissa Best, van Emde Boas ja Lenstra [4] . Skorpionigraafi on graafi, joka sisältää polun, joka koostuu kolmesta kärjestä siten, että polun yksi päätypiste on yhteydessä kaikkiin muihin graafin kärkipisteisiin, kun taas polun kaksi jäljellä olevaa kärkeä ovat yhteydessä vain itse polun kärkipisteisiin .

Sitten Aanderaa ja Rosenberg muotoilivat uuden olettamuksen ( Aanderaa-Rosenberg- hypoteesi ), jonka mukaan sen ratkaiseminen, onko graafilla ei-triviaali monotoninen ominaisuus, vaatii kyselyitä [5] . Tämän olettamuksen ratkaisivat Raivest ja Vuillemin [1] osoittaen, että ainakin kyselyitä tarvitaan testaamaan mitä tahansa ei-triviaalia monotonista ominaisuutta. Myöhemmin rajaa parannettiin Kleitmaniksi ja Kwiatkowskiksi [6] , sitten Kahniksi, Sachsiksi ja Sturtevantiksi [7] , Kornefeliksi ja Trishiksi [8] sekä Scheiderweileriksi ja Trishiksi [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 esitti tiukemman väitteen (joita kutsutaan nykyään kovuusolettamukseksi tai Aandera-Karp-Rosenberg-oletukseksi ), että "mikä tahansa ei-triviaali monotoninen ominaisuus n pisteessä olevien graafien on kova" [10] . Ominaisuuden sanotaan olevan vaikea , jos sen määrittäminen, onko graafilla annettu ominaisuus, vaatii kyselyitä [11] . Tämä olettamus väittää, että paras algoritmi minkä tahansa ei-triviaalin monotonisen ominaisuuden testaamiseen on (pahimmassa tapauksessa) kysellä kaikki mahdolliset reunat. Tämä arvelu jää avoimeksi, vaikka jotkin graafien erityisominaisuudet on osoitettu olevan vaikeita kaikille n :ille . Kahn, Sacks ja Sturtevant [7] ratkaisivat oletuksen tapaukselle, jossa n on alkuluvun potenssi, topologisella lähestymistavalla. Yao [12] ratkaisi oletuksen kaikille kaksiosaisten graafien ei-triviaalisille monotoniominaisuuksille . On myös osoitettu, että pienet suljetut kiinteistöt ovat myös vaikeita suurille n :ille [13] . ${\tfrac {n(n-1)}{2))$

Probabilistisen kyselyn monimutkaisuus

Richard Karp arveli myös, että kyselyitä tarvitaan ei-triviaalisten monotonisuusominaisuuksien testaamiseen, vaikka todennäköisyysalgoritmit olisivat sallittuja. Ei tunneta ei-triviaalista ominaisuutta, jonka tarkistaminen vaatisi vähemmän kyselyitä. Lineaarinen alaraja (eli kaikille monotonisille ominaisuuksille seuraa hyvin yleisestä suhteesta todennäköisyyden ja deterministisen kyselyn monimutkaisuuden välillä . Ensimmäisen superlineaarisen alarajan kaikille monotonisille invarianteille antoi Yao [14] , joka osoitti, että Sen jälkeen King [15] paransi sen arvoon , ja sitten Hainal [16] arvoon . Tämä tulos parannettiin sitten nykyiseen hyvin tunnettuun Chakrabartin ja Khotin rajan arvoon [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)$

Jotkut viimeaikaiset tulokset antavat alarajoja, jotka määräytyvät kyseessä olevan graafin monotonisen ominaisuuden kriittisen todennäköisyyden p mukaan. Kriittinen todennäköisyys p määritellään ainoaksi p : ksi, jolla satunnaisgraafilla G ( n , p ) on tämä ominaisuus todennäköisyydellä 1/2. Satunnainen graafi G ( n , p ) on graafi, jossa on n kärkeä, jossa jokainen reuna on läsnä todennäköisyydellä p ja reunan olemassaolo/puuttuminen ei riipu kaikista muista reunoista. Friedgood, Kahn ja Wigderson [18] osoittivat, että mikä tahansa monotoninen graafin invariantti kriittisellä todennäköisyydellä p vaatii kyselyitä. Samaan ongelmaan O'Donnell, Sacks, Schramm ja Servedio [19] osoittivat alarajan . $\Omega \left(\min \left\({\frac {n}{\min(p,1-p))),{\frac {n^{2)){\log n))\ oikea\}\oikea)$ $\Omega ({\frac {n^{\tfrac {4}{3))}{p^{\tfrac {1}{3)))))$

Kuten deterministisessä tapauksessa, on monia erikoisinvariantteja, joiden alaraja tunnetaan. Lisäksi joillekin graafiinvarianttien luokille tunnetaan paremmat rajat. Esimerkiksi sen testaamiseksi, onko graafissa aligraafi, joka on isomorfinen jonkin tietyn graafin kanssa (ns. isomorfinen osagraafiongelma ), Grögerin mukaan tunnetuin alaraja on [20] . $\Omega (n^{2})$ $\Omega (n^{\tfrac {3}{2)))$

Kvanttikyselyn monimutkaisuus

Tasaisesti rajoittuneelle kyselyn kvanttikompleksivirheelle tunnetuin alaraja on , kuten Andrew Yao huomautti (tulosta ei julkaista, mutta se mainitaan [21] ). Raja saadaan yhdistämällä todennäköisyyspohjainen alaraja kvanttivastustajamenetelmään . Paras alaraja, jonka toivotaan saavuttavan, on , toisin kuin klassisessa tapauksessa, Groverin algoritmin ansiosta, joka tarjoaa algoritmin O( n )-kyselyillä testaamaan tyhjyyden monotonista ominaisuutta. Determinististen ja todennäköisyyksien tapausten tapaan on joitakin ominaisuuksia, joilla tiedetään olevan alaraja , kuten ei-tyhjyys (joka seuraa Groverin algoritmin optimaalisuudesta) ja ominaisuus sisältää kolmion . Joillakin graafiinvarianteilla tiedetään olevan alaraja , ja on jopa ominaisuuksia, joilla on alaraja . Esimerkiksi monotoninen ei-tasoisuusominaisuus vaatii kyselyitä [22] ja monotoninen ominaisuus, joka sisältää yli puolet mahdollisista reunoista (kutsutaan myös enemmistöfunktioksi), vaatii kyselyitä [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})$

Muistiinpanot

↑ 1 2 Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ Tämä valuman määritelmä eroaa tavallisesta valuman määritelmästä. Tämä määritelmä olettaa, että kaikki graafin kaaret tulevat yhteen kärkeen (nielu), kun taas tavallinen määritelmä olettaa vain, että nielusta ei ole lähteviä kaaria (katso " Graafin kärkien tyypit ").
↑ 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 .
↑ Kuningas, 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 ym., 2008 .
↑ Beals, Buhrman, Cleve, Mosca, de Wolf, 2001 .

Kirjallisuus

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Boolen funktioiden kvanttikyselyn monimutkaisuus pienillä on-joukoilla // Proceedings of the 19th International Symposium on Algorithms and Computation. - Gold Coast, Australia: Springer-Verlag , 2008. - T. 5369. - P. 907-918. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - 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. Kvanttialarajat polynomeilla // Journal of the ACM . - 2001. - T. 48 , no. 4 . — S. 778–797 . - doi : 10.1145/502090.502097 . — arXiv : quant-ph/9802049 . .
Paras MR, van Emde Boas P., Lenstra HW Teroitettu versio Aanderaa-Rosenbergin arvelusta. - Mathematisch Centrum Amsterdam , 1974. - (Raportti ZW 30/74).
Amit Chakrabarti, Subhash Khot . Parannetut alarajat graafisten ominaisuuksien satunnaistetulle monimutkaiselle // 28. kansainvälisen automaatteja, kieliä ja ohjelmointia käsittelevän kollokvion julkaisut. - Springer-Verlag, 2001. - T. 2076. - S. 285-296. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-42287-7 . - doi : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot , Yaoyun Shi. Aligraafin sisältämisen välttely ja siihen liittyvät ominaisuudet // SIAM Journal on Computing . - 2001. - T. 31 , no. 3 . — S. 866–875 . - doi : 10.1137/S0097539700382005 . .
Ehud Friedgut, Jeff Kahn, Avi Wigderson . Kuvaajan ominaisuuksien laskeminen satunnaistettujen alikuutio-osioiden mukaan // Tietojenkäsittelytieteen satunnais- ja approksimaatiotekniikat. - Springer-Verlag , 2002. - T. 2483. - S. 953. - (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-540-44147-2 . - doi : 10.1007/3-540-45726-7_9 . .
Hans Dietmar Groger. Monotonisen graafin ominaisuuksien satunnaistetusta monimutkaisuudesta // Acta Cybernetica. - 1992. - T. 10 , no. 3 . — S. 119–127 . Arkistoitu alkuperäisestä 24. syyskuuta 2015. .
Peter Hajnal. Ω( n 4/3 ) alaraja graafin ominaisuuksien satunnaistetulle kompleksisuudelle // Combinatorica . - 1991. - T. 11 , no. 2 . — s. 131–143 . - doi : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. Topologinen lähestymistapa välttelyyn // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium tietojenkäsittelytieteen perusteista . - Los Alamitos, CA, USA: IEEE Computer Society, 1983. - S. 31–33. - ISBN 0-8186-0508-1 . - doi : 10.1109/SFCS.1983.4 . .
Valerie King. Kuvaajan ominaisuuksien monimutkaisuuden alarajat // Proc. 20. ACM Symposium on Theory of Computing . - Chicago, Illinois, Yhdysvallat, 1988. - s . 468-476 . — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Lisää tuloksia Aanderaa-Rosenbergin olettamuksesta // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 . — S. 85–95 . - doi : 10.1016/0095-8956(80)90057-X .
Dmitri Kozlov. Kombinatorinen algebrallinen topologia. - Springer-Verlag, 2008. - ISBN 978-3-540-73051-4 .
Frank H. Lutz. Joitakin väistämisarvaukseen liittyviä tuloksia // Journal of Combinatorial Theory, Series B. - 2001. - V. 81 , no. 1 . — S. 110–124 . - doi : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. Asymptoottinen rajoitus monotonisen graafin ominaisuuksien kompleksisuudelle // 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. Kvanttialgoritmit kolmioongelmalle // Proceedings of the kuudestoista vuotuinen 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. Jokaisella päätöspuulla on vaikutusvaltainen muuttuja // 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. Yleistys ja todiste Aanderaa-Rosenberg-oletuksesta // Proc. 7. ACM-symposium tietojenkäsittelyteoriasta . - Albuquerque, New Mexico, Yhdysvallat, 1975. - S. 6-11. - doi : 10.1145/800116.803747 . .
Arnold L. Rosenberg. Aika, joka tarvitaan graafien ominaisuuksien tunnistamiseen: ongelma // SIGACT News. - 1973. - V. 5 , no. 4 . - S. 15-16 . - doi : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. Monotonisten graafisten ominaisuuksien monimutkaisuuden alaraja // SIAM Journal on Discrete Mathematics. - 2013. - T. 27 , nro 1 . — S. 257–265 . - doi : 10.1137/120888703 .
Eberhard Triesch. Joidenkin graafin ominaisuuksien tunnistamisen monimutkaisuudesta // Combinatorica . - 1996. - T. 16 , no. 2 . — S. 259–268 . - doi : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Monotonisen kaksiosaisen graafin ominaisuudet ovat vältteleviä // SIAM Journal on Computing . - 1988. - T. 17 , no. 3 . — S. 517–520 . - doi : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Graafin ominaisuuksien satunnaistettujen algoritmien alarajat // Journal of Computer and System Sciences . - 1991. - T. 42 , no. 3 . — S. 267–287 . - doi : 10.1016/0022-0000(91)90003-N . .

Lue lisää lukemista varten

Bela Bollobas. Luku VIII. Monimutkaisuus ja pakkaus // 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. Tutkimus Evasiveness: Alarajat Boolen funktioiden päätöspuun monimutkaisuudesta. – 1990.
Michael Sax. Päätöspuut: ongelmat ja tulokset, vanha ja uusi . Haettu 17. helmikuuta 2019. Arkistoitu alkuperäisestä 3. maaliskuuta 2016. (määrätön)