Ipoteza Aanderaa-Karp-Rosenberg

Probleme nerezolvate de informatică : Demonstrați sau infirmați conjectura Aanderaa-Karp-Rosenberg.

Ipoteza Aandera-Karp-Rosenberg (cunoscută și ca ipoteza Aandera-Rosenberg sau ipoteza dificultății ) este un grup de ipoteze înrudite despre numărul de întrebări sub forma „Există o margine între vârful u și vârful v ?” care trebuie se răspunde pentru a determina dacă un graf nedirecționat are sau nu o anumită proprietate (invariantă), cum ar fi a fi planar sau bipartit . Ipoteza este numită după matematicianul norvegian Stol Aanderaa și oamenii de știință americani Richard M. Karp și Arnold L. Rosenberg. Conform ipotezei, pentru o clasă largă de invarianți, niciun algoritm nu poate garanta că un algoritm poate omite orice interogare - orice algoritm pentru a determina dacă un graf are o proprietate, indiferent cât de inteligent este acest algoritm, trebuie să verifice fiecare pereche de vârfuri înainte dând un răspuns. O proprietate care satisface ipoteza se numește hard .

Mai exact, conjectura Aandera-Rosenberg afirmă că orice algoritm determinist trebuie să testeze cel puțin o fracțiune fixă din toate perechile posibile de vârfuri pentru a determina, în cel mai rău caz, proprietate monotonă netrivială a grafului. În acest context, o proprietate este monotonă dacă rămâne adevărată la adăugarea muchiilor (deci proprietatea de planaritate nu este monotonă, dar proprietatea de nonplanaritate este monotonă). O versiune mai riguroasă a acestei presupuneri, numită ipoteza dificultății sau conjectura Aandera-Karp-Rosenberg, afirmă că exact testele sunt necesare. Au fost formulate și studiate versiuni ale problemei pentru algoritmi probabilistici și cuantici . ${\tfrac {n(n-1)}{2))$

Conjectura deterministă Aanderaa-Rosenberg a fost dovedită de Rivest și Willemin [1] , dar conjectura mai puternică Aanderaa-Karp-Rosenberg rămâne nedovedită. De asemenea, există o mare diferență între limita inferioară și cea mai bună limită inferioară dovedită pentru complexitatea probabilistică și cuantică în funcție de numărul de interogări.

Exemplu

Proprietatea de a nu fi gol (adică de a avea cel puțin o muchie) este monotonă, deoarece adăugarea unei alte muchii la un graf nevid produce un graf nevid. Există un algoritm simplu pentru a testa dacă un grafic nu este gol - treceți în buclă prin toate perechile de vârfuri și verificați dacă fiecare pereche este conectată printr-o muchie. Dacă se găsește o muchie în acest fel, întrerupem bucla și raportăm că graficul nu este gol, iar dacă bucla se termină fără a găsi vreo muchie, atunci raportăm că graficul este gol. Pe astfel de grafice (de exemplu, grafice complete ), acest algoritm se termină rapid fără a verifica fiecare pereche de vârfuri, dar pe un grafic gol, algoritmul verifică toate perechile posibile înainte de a se termina. Prin urmare, complexitatea algoritmului pentru interogări este egală - în cel mai rău caz, algoritmul efectuează verificări. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Algoritmul descris mai sus nu este singura metodă posibilă pentru verificarea non-vidității, dar rezultă din conjectura Aandera-Karp-Rosenberg că orice algoritm determinant pentru verificarea non-vidității are aceeași complexitate a interogării . Adică, proprietatea de a nu fi gol este dificilă . Pentru această proprietate, rezultatul este ușor de verificat direct - dacă algoritmul nu efectuează verificări, nu va putea distinge între un grafic gol și un grafic care conține o margine a unei perechi de vârfuri neverificate și trebuie să dea un răspuns incorect pentru unul dintre aceste două grafice (fie pentru unul gol, fie pentru un grafic cu muchie). ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Definiții

În sensul acestui articol, toate graficele vor fi simple și nedirecționate , dacă nu se specifică altfel. Aceasta înseamnă că muchiile graficului formează o mulțime (dar nu o mulțime multiplă ), iar capetele fiecărei muchii sunt o pereche de vârfuri distincte. Se presupune că graficele au o reprezentare implicită în care fiecare vârf are un identificator sau o etichetă unică și în care se poate verifica adiacența a două vârfuri, dar numai operațiunile de bază pot fi efectuate în graficul de adiacență.

În mod informal, o proprietate de graf (sau invariant de graf, ambii termeni sunt folosiți interschimbabil în acest articol) este o proprietate a unui graf care este independentă de marcaj. Mai formal, o proprietate de grafic este o mapare din setul tuturor graficelor la {0,1} astfel încât graficele izomorfe se mapează la aceeași valoare. De exemplu, proprietatea de a conține cel puțin un vârf de gradul 2 este un invariant de grafic, dar proprietatea că primul vârf are gradul 2 nu este un invariant de grafic, deoarece proprietatea depinde de etichetarea graficului (în special, aceasta depinde de ce vârf este considerat „primul „). Un invariant de grafic se numește non-trivial dacă nu are aceeași valoare pentru toate graficele. De exemplu, proprietatea de a fi un grafic este o proprietate banală, deoarece toate graficele au această proprietate. Dar, pe de altă parte, proprietatea de a fi gol este non-trivială, deoarece un graf gol are această proprietate, dar unul nevid nu o are. Se spune că o proprietate a unui grafic este monotonă dacă adăugarea muchiilor nu distruge proprietățile. Alternativ, dacă un graf are proprietatea monotonă, atunci orice supergraf al acelui graf de pe același set de vârfuri are și această proprietate. De exemplu, proprietatea de a fi neplanar este monotonă - supergraful unui graf neplanar este, de asemenea, neplanar. Cu toate acestea, proprietatea de a fi regulat nu este monotonă.

Notația „O” este adesea folosită pentru complexitatea interogărilor . Pe scurt, f ( n ) este dacă pentru orice suficient de mare pentru o constantă pozitivă c . În mod similar, f ( n ) este dacă pentru suficient de mare pentru o constantă pozitivă c . În cele din urmă, f ( n ) este dacă este atât , cât și . $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))$

Complexitatea cererii

Complexitatea unei interogări deterministe pentru a evalua o funcție de n biți este egală cu numărul de biți x i pe care algoritmul determinist trebuie să-i citească în cel mai rău caz pentru a determina valoarea funcției. De exemplu, dacă funcția ia valoarea 0 dacă toți biții sunt 0 și valoarea 1 în caz contrar (adică funcția SAU ), atunci complexitatea interogărilor deterministe este exact n . În cel mai rău caz, primii n − 1 biți citiți vor fi 0, iar valoarea funcției va depinde doar de ultimul bit. Dacă algoritmul nu citește acest bit, poate da un răspuns incorect. Numărul de biți citiți se mai numește și numărul de solicitări făcute pe intrare. Se poate imagina că algoritmul cere (efectuează o solicitare) o intrare despre un anumit bit și intrarea răspunde la această solicitare. $(x_{1},x_{2},\dots ,x_{n})$

Complexitatea unei cereri de funcție probabilistică este definită în mod similar, cu excepția faptului că algoritmul poate fi probabilistic, adică poate arunca o monedă și poate folosi partea rulată a monedei pentru a decide ce bit să solicite. Cu toate acestea, algoritmul probabilistic trebuie să continue să ofere răspunsuri corecte la toate solicitările de intrare - erorile nu sunt permise. Astfel de algoritmi sunt numiți algoritmi Las Vegas și ar trebui să fie distinși de algoritmii Monte Carlo , în care sunt permise unele erori. Complexitatea unei interogări probabilistice poate fi definită în sensul lui Monte Carlo, dar conjectura Aandera-Karp-Rosenberg vorbește despre complexitatea interogărilor pentru invarianții de grafic în sensul Las Vegas.

Complexitatea cuantică a interogărilor este o generalizare naturală a complexității unei interogări probabilistice, în mod firesc cu rezoluția interogărilor și răspunsurilor cuantice. Complexitatea interogărilor cuantice poate fi definită și în termeni de algoritmi Monte Carlo sau algoritmi Las Vegas, dar se înțelege de obicei algoritmii Monte Carlo cuantici.

În contextul acestei ipoteze, funcția calculată este o proprietate a graficului, iar intrarea este un șir de dimensiune , care specifică locația muchiilor pe un grafic cu n vârfuri, deoarece un grafic poate avea maximum de muchii. Complexitatea solicitării oricărei funcții este delimitată de mai sus de valoarea , deoarece întreaga intrare va fi citită după solicitări, ceea ce determină întregul grafic de intrare. ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$ ${\tfrac {n(n-1)}{2))$

Complexitatea interogărilor deterministe

Pentru algoritmii determiniști, Rosenberg [2] a sugerat că pentru toate proprietățile netriviale ale graficelor de pe n vârfuri, a decide dacă un graf are această proprietate necesită interogări. Este clar că este necesară o condiție non-trivială, deoarece există proprietăți triviale precum „Este acesta un grafic?”, la care se poate răspunde fără nicio interogare. $\Omega (n^{2})$

Ipoteza a fost respinsă de Aanderaa, care a propus o proprietate a unui graf direcționat (proprietatea de a avea o „chiuvetă”), a cărui verificare necesită doar interogări O( n ). Un sink într-un graf direcționat este un vârf care are gradul în interior n -1 și gradul în exterior 0 [3] . Această proprietate poate fi verificată în mai puțin de 3n interogări [4] . O proprietate a unui graf nedirecționat care poate fi verificată în interogările O( n ) este proprietatea „graful este un graf scorpion”, descrisă mai întâi în Best, van Emde Boas și Lenstra [4] . Un grafic scorpion este un grafic care conține o cale constând din trei vârfuri, astfel încât un vârf de capăt al căii este conectat la toate celelalte vârfuri ale graficului, în timp ce cele două vârfuri rămase ale căii sunt conectate numai la vârfurile căii în sine. .

Apoi Aanderaa și Rosenberg au formulat o nouă presupunere (ipoteza Aanderaa-Rosenberg ), care afirmă că a decide dacă un graf are o proprietate monotonă netrivială necesită interogări [5] . Această presupunere a fost rezolvată de Raivest și Vuillemin [1] , arătând că sunt necesare cel puțin interogări pentru a testa orice proprietate monotonă netrivială. Granița a fost mai târziu îmbunătățită la Kleitman și Kwiatkowski [6] , apoi la Kahn, Sachs și Sturtevant [7] , la Kornefel și Trish [8] și la Scheiderweiler și 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 a făcut o afirmație mai riguroasă (numită acum conjectura durității sau conjectura Aandera–Karp–Rosenberg ) că „orice proprietate monotonă netrivială a graficelor pe n vârfuri este grea” [10] . Se spune că o proprietate este grea dacă determinarea dacă graficul are proprietatea dată necesită interogări [11] . Această presupunere afirmă că cel mai bun algoritm pentru testarea oricărei proprietăți monotone non-triviale este de a (în cel mai rău caz) interogarea tuturor marginilor posibile. Această presupunere rămâne deschisă, deși unele proprietăți speciale ale graficelor s-au dovedit a fi dificile pentru toți n . Conjectura a fost rezolvată pentru cazul în care n este o putere a unui număr prim de Kahn, Sacks și Sturtevant [7] folosind o abordare topologică . Conjectura a fost rezolvată pentru toate proprietățile monotone non-triviale ale grafurilor bipartite de către Yao [12] . De asemenea, sa demonstrat că proprietățile minore închise sunt dificile și pentru n mari [13] . ${\tfrac {n(n-1)}{2))$

Complexitatea unei interogări probabilistice

Richard Karp a mai presupus că interogările sunt necesare pentru a testa proprietățile de monotonitate non-triviale, chiar dacă algoritmii probabilistici sunt permisi. Nu se cunoaște nicio proprietate netrivială care să necesite mai puține interogări pentru verificare. O limită inferioară liniară (adică pentru toate proprietățile monotone rezultă dintr-o relație foarte generală între complexitățile de interogare probabilistică și deterministă . Prima limită inferioară superliniară pentru toți invarianții monotoni a fost dată de Yao [14] , care a arătat că sunt necesare interogări.A fost apoi îmbunătățit de King [15 ] la , și apoi de Hainal [16] la , Acest rezultat a fost apoi îmbunătățit la valoarea actuală bine-cunoscută a limitei Chakrabarti și 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)$

Unele rezultate recente dau limite inferioare care sunt determinate de probabilitatea critică p a proprietății monotone a graficului în cauză. Probabilitatea critică p este definită ca singurul p astfel încât graficul aleatoriu G ( n , p ) are această proprietate cu probabilitate 1/2. Un grafic aleatoriu G ( n , p ) este un grafic cu n vârfuri în care fiecare muchie este prezentă cu probabilitate p și prezența/absența unei muchii nu depinde de toate celelalte muchii. Friedgood, Kahn și Wigderson [18] au arătat că orice invariant de grafic monoton cu probabilitate critică p necesită interogări. Pentru aceeași problemă, O'Donnell, Sacks, Schramm și Servedio [19] au arătat o limită inferioară pe . $\Omega \left(\min \left\({\frac {n}{\min(p,1-p)}), {\frac {n^{2}} {\log n))\ corect corect)$ $\Omega ({\frac {n^{\tfrac {4}{3)}}{p^{\tfrac {1}{3))))}$

Ca și în cazul determinist, există mulți invarianți speciali pentru care este cunoscută limita inferioară . Mai mult decât atât, sunt cunoscute limite mai bune pentru unele clase de invarianți de grafic. De exemplu, pentru a testa dacă un graf are un subgraf izomorf cu un graf dat (așa-numita problemă a subgrafului izomorf ), cea mai cunoscută limită inferioară, conform lui Gröger, este [20] . $\Omega (n^{2})$ $\Omega (n^{\tfrac {3}{2))}$

Complexitatea interogării cuantice

Pentru o eroare de complexitate cuantică a interogării delimitată uniform , cea mai cunoscută limită inferioară este , după cum a observat Andrew Yao (rezultatul nu este publicat, dar este menționat în [21] ). Limita este obținută prin combinarea unei limite inferioare probabilistice cu o metodă adversar cuantic . Cea mai bună limită inferioară pe care o sperăm să o obțină este , spre deosebire de cazul clasic, datorită algoritmului lui Grover , care oferă un algoritm cu interogări O( n ) pentru a testa proprietatea monotonă a nevidității. Similar cu cazurile deterministe și probabilistice, există unele proprietăți despre care se știe că au o limită inferioară , cum ar fi non-emptiness (care decurge din optimitatea algoritmului lui Grover) și proprietatea de a conține un triunghi . Există unele invariante de grafică cunoscute ca având o limită inferioară și există chiar proprietăți cu o limită inferioară . De exemplu, proprietatea monotonă de non-planaritate necesită interogări [22] , iar proprietatea monotonă de a conține mai mult de jumătate din muchiile posibile (numită și funcție majoritară) necesită interogări [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})$

Note

↑ 1 2 Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ Această definiție a scurgerii diferă de definiția obișnuită a scurgerii. Această definiție presupune că toate arcele de graf intră într-un vârf (sink), în timp ce definiția obișnuită presupune doar că nu există arce de ieșire din sink (vezi „ Tipuri de vârfuri de graf ”).
↑ 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 , p. 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 .

Literatură

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Complexitatea interogării cuantice a funcțiilor booleene cu seturi mici // Proceedings of the 19th International Symposium on Algorithms and Computation. - Gold Coast, Australia: Springer-Verlag , 2008. - T. 5369. - P. 907-918. — (Note de curs în Informatică). - 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. Limite inferioare cuantice prin polinoame // Jurnalul 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 O versiune ascuțită a conjecturei Aanderaa-Rosenberg. - Mathematisch Centrum Amsterdam , 1974. - (Raport ZW 30/74).
Amit Chakrabarti, Subhash Khot . Limite inferioare îmbunătățite ale complexității randomizate a proprietăților graficelor // Proceedings of the 28th International Colocvium on Automata, Languages and Programming. - Springer-Verlag, 2001. - T. 2076. - S. 285-296. — (Note de curs în Informatică). — ISBN 978-3-540-42287-7 . - doi : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot, Yaoyun Shi. Evazivitatea reținerii subgrafelor și proprietățile aferente // SIAM Journal on Computing . - 2001. - T. 31 , nr. 3 . — S. 866–875 . - doi : 10.1137/S0097539700382005 . .
Ehud Friedgut, Jeff Kahn, Avi Wigderson . Calcularea proprietăților grafului prin partiții ale subcuburilor randomizate // Tehnici de randomizare și aproximare în informatică. - 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. Despre complexitatea randomizată a proprietăților graficelor monotone // Acta Cybernetica. - 1992. - T. 10 , nr. 3 . — S. 119–127 . Arhivat din original pe 24 septembrie 2015. .
Peter Hajnal. O limită inferioară Ω( n 4/3 ) a complexității randomizate a proprietăților graficului // Combinatorica . - 1991. - T. 11 , nr. 2 . — p. 131–143 . - doi : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. O abordare topologică a evazivității // Al 24-lea simpozion anual privind fundamentele informaticii (sfcs 1983). Simpozion despre fundamentele informaticii . - Los Alamitos, CA, SUA: IEEE Computer Society, 1983. - P. 31-33. - ISBN 0-8186-0508-1 . - doi : 10.1109/SFCS.1983.4 . .
Valerie King. Limitele inferioare ale complexității proprietăților graficului // Proc. Al 20-lea Simpozion ACM de Teoria Calculului . - Chicago, Illinois, Statele Unite ale Americii, 1988. - pp . 468-476 . — ISBN 0-89791-264-0 . - doi : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Rezultate suplimentare despre conjectura Aanderaa-Rosenberg // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 . — S. 85–95 . - doi : 10.1016/0095-8956(80)90057-X .
Dmitri Kozlov. Topologie algebrică combinatorică. - Springer-Verlag, 2008. - ISBN 978-3-540-73051-4 .
Frank H. Lutz. Câteva rezultate legate de conjectura evaziunii // Journal of Combinatorial Theory, Seria B. - 2001. - V. 81 , nr. 1 . — S. 110–124 . - doi : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. O limită asimptotică pentru complexitatea proprietăților graficelor monotone // 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. Algoritmi cuantici pentru problema triunghiului // Lucrările celui de-al șaisprezecelea simpozion anual ACM-SIAM despre algoritmi discreti . — Vancouver, British Columbia: Society for Industrial and Applied Mathematics , 2005. — pp. 1109–1117. .
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Fiecare arbore de decizie are o variabilă influentă // 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. O generalizare și o dovadă a conjecturei Aanderaa-Rosenberg // Proc. Al 7-lea Simpozion ACM despre Teoria Calculului . - Albuquerque, New Mexico, Statele Unite ale Americii, 1975. - S. 6-11. - doi : 10.1145/800116.803747 . .
Arnold L. Rosenberg. Despre timpul necesar recunoașterii proprietăților graficelor: o problemă // SIGACT News. - 1973. - V. 5 , nr. 4 . — S. 15–16 . - doi : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. O limită inferioară pentru complexitatea proprietăților graficelor monotone // SIAM Journal on Discrete Mathematics. - 2013. - T. 27 , Nr. 1 . — S. 257–265 . - doi : 10.1137/120888703 .
Eberhard Triesch. Despre complexitatea recunoașterii unor proprietăți de graf // Combinatorică . - 1996. - T. 16 , nr. 2 . — S. 259–268 . - doi : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Proprietățile graficului bipartit monoton sunt evazive // SIAM Journal on Computing . - 1988. - T. 17 , nr. 3 . — S. 517–520 . - doi : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Limitele inferioare ale algoritmilor randomizati pentru proprietățile graficului // Journal of Computer and System Sciences . - 1991. - T. 42 , nr. 3 . — S. 267–287 . - doi : 10.1016/0022-0000(91)90003-N . .

Lectură pentru lecturi suplimentare

Bela Bollobas. Capitolul VIII. Complexitate și ambalare // Teoria grafurilor extreme. — New York: Dover Publications , 2004. — pp. 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. Un studiu al evazivității: limite inferioare ale complexității arborelui de decizie a funcțiilor booleene. — 1990.
Michael Sax. Arbori de decizie: probleme și rezultate, vechi și noi . Consultat la 17 februarie 2019. Arhivat din original pe 3 martie 2016. (nedefinit)