Przypuszczenie Aanderaa – Karpa – Rosenberga

Nierozwiązany problem w informatyce :

Udowodnić lub obalić hipotezę Aanderaa – Karpa – Rosenberga.

(więcej nierozwiązanych problemów w informatyce)

W informatyce teoretycznej hipoteza Aanderaa – Karpa – Rosenberga (znana również jako hipoteza Aanderaa – Rosenberga lub hipoteza evasiveness ) to grupa powiązanych przypuszczeń dotyczących liczby pytań w postaci „Czy istnieje krawędź między wierzchołkiem ${\ displaystyle u}$ i wierzchołek ${\ displaystyle v}$ ?" na które należy odpowiedzieć, aby określić, czy graf nieskierowany ma określoną właściwość, taką jak planarność lub dwudzielność . Zostały nazwane na cześć Ståla Aanderaa , Richarda M. Karpa i Arnolda L. Rosenberga . Zgodnie z przypuszczeniem, dla szerokiej klasy właściwości żaden algorytm nie może zagwarantować, że będzie w stanie pominąć jakiekolwiek pytania: każdy algorytm do określania, czy graf ma tę właściwość, bez względu na to, jak sprytny, może wymagać zbadania każdej pary wierzchołków zanim będzie mógł udzielić odpowiedzi. Właściwość spełniająca to przypuszczenie nazywa się evasive .

Dokładniej, hipoteza Aanderaa-Rosenberga stwierdza, że ​​​​każdy algorytm deterministyczny musi przetestować co najmniej stały ułamek wszystkich możliwych par wierzchołków, w najgorszym przypadku , aby określić jakąkolwiek nietrywialną właściwość wykresu monotonicznego; w tym kontekście właściwość jest monotoniczna, jeśli pozostaje prawdziwa po dodaniu krawędzi (więc planarność nie jest monotoniczna, ale nieplanarność jest monotoniczna). Silniejsza wersja tego przypuszczenia, zwana hipotezą unikania lub hipotezą Aanderaa – Karpa – Rosenberga, stwierdza, że ​​dokładnie $n(n-1)/2} .$${\ Displaystyle {\ tbinom {n} {2}} =$ Potrzebne są testy Sformułowano i zbadano również wersje problemu dla algorytmów losowych i algorytmów kwantowych .

Deterministyczna hipoteza Aanderaa-Rosenberga została udowodniona przez Rivesta i Vuillemina (1975) , ale silniejsza hipoteza Aanderaa-Karpa-Rosenberga pozostaje nieudowodniona. Ponadto istnieje duża różnica między domniemaną dolną granicą a najlepiej sprawdzoną dolną granicą złożoności zapytań losowych i kwantowych.

Przykład

Właściwość bycia niepustym (to znaczy posiadania co najmniej jednej krawędzi) jest monotoniczna, ponieważ dodanie kolejnej krawędzi do niepustego wykresu tworzy kolejny niepusty graf. Istnieje prosty algorytm sprawdzania, czy graf jest niepusty: wykonaj pętlę przez wszystkie pary wierzchołków, sprawdzając, czy każda para jest połączona krawędzią. Jeśli kiedykolwiek w ten sposób zostanie znaleziona krawędź, wyrwij się z pętli i zgłoś, że graf nie jest pusty, a jeśli pętla zakończy się bez znalezienia krawędzi, zgłoś, że graf jest pusty. Na niektórych grafach (na przykład pełnych grafach ) ten algorytm zakończy się szybko, bez sprawdzania każdej pary wierzchołków, ale na pustym grafie sprawdza wszystkie możliwe pary przed zakończeniem. Dlatego złożoność zapytania tego algorytmu wynosi ${\ Displaystyle {\ tbinom {n} {2}} = n (n-1)/2}$ : w najgorszym przypadku , algorytm wykonuje testy ${\ Displaystyle n (n-1)/2} .$

Algorytm opisany powyżej nie jest jedyną możliwą metodą testowania niepustości, ale hipoteza Aanderaa – Karpa – Rosenberga implikuje, że każdy deterministyczny algorytm testowania niepustości ma tę samą złożoność zapytania w najgorszym przypadku, ${\ displaystyle n (n-1) / 2}$ . Oznacza to, że właściwość bycia niepustym jest wymijająca . W przypadku tej właściwości $,$ jeśli algorytm nie wykonuje może odróżnić pustego wykresu od wykresu ma jedną krawędź łączącą jedną z nieprzetestowanych par wierzchołków i musi dać błędną odpowiedź na jednym z tych dwóch wykresów.

Definicje

W kontekście tego artykułu wszystkie grafy będą proste i nieskierowane , chyba że zaznaczono inaczej. Oznacza to, że krawędzie grafu tworzą zbiór (a nie multizbiór ) , a każda krawędź jest parą odrębnych wierzchołków. Zakłada się, że grafy mają niejawną reprezentację , w której każdy wierzchołek ma unikalny identyfikator lub etykietę i w której można przetestować przyleganie dowolnych dwóch wierzchołków, ale dla którego testowanie przylegania jest jedyną dozwoloną operacją pierwotną.

Nieformalnie właściwość wykresu jest właściwością wykresu, która jest niezależna od etykietowania. Bardziej $formalnie , właściwość wykresu$ odwzorowaniem z klasy wszystkich wykresów na takie że wykresy izomorficzne są odwzorowywane na tę samą Na przykład właściwość zawierania co najmniej jednego wierzchołka stopnia drugiego jest właściwością grafu, ale właściwość pierwszego wierzchołka stopnia drugiego już nią nie jest, ponieważ zależy to od oznaczenia grafu (w szczególności zależy od tego, który wierzchołek jest „pierwszym” wierzchołkiem). Właściwość grafu nazywana jest nietrywialną, jeśli nie przypisuje tej samej wartości wszystkim wykresom. Na przykład właściwość bycia grafem jest właściwością trywialną, ponieważ wszystkie grafy posiadają tę właściwość. Z drugiej strony właściwość bycia pustym nie jest trywialna, ponieważ pusty graf posiada tę właściwość, ale niepuste grafy nie. Mówimy, że graf jest monotoniczny , jeśli dodanie krawędzi nie niszczy tej właściwości. Alternatywnie, jeśli graf posiada właściwość monotoniczności, to każdy supergraf tego grafu w tym samym zbiorze wierzchołków również ją posiada. Na przykład właściwość bycia niepłaskim jest monotoniczna: supergraf niepłaskiego grafu sam w sobie jest niepłaski. Jednak właściwość bycia regularnym nie jest monotonna.

dużego O jest często używana do opisania złożoności zapytania. W $sol$$jest$ czytane $_ (n)}$ _ ") jeśli istnieją stałe dodatnie $Displaystyle$ N $N}$ takie, że dla wszystkich ${\ Displaystyle n \ geq N$ } ${\ Displaystyle f (n) \ równoważnik c \ cdot g (n)}$ . Podobnie ${\ Displaystyle f (n)}$ jest ${\ Displaystyle \ Omega (g (n)}}$ , jeśli istnieją stałe dodatnie $c}$ N $N}$$\ Displaystyle$ takie, że dla wszystkich ${\ Displaystyle n \ geq N}$ , ${\ Displaystyle f (n) \ geq c \ cdot g (n)}$ . Wreszcie $sol$$Displaystyle$$_ g (n))}$ n _ i ${\ Displaystyle \ Omega (g (n))}$ .

Złożoność zapytania

Deterministyczna złożoność zapytania oceny funkcji na $($ gdzie bity mogą być oznaczone jako ${\ displaystyle x_ {1}, x_ {2}, \ kropki x_ { n}}$ ) to liczba bitów $najgorszym$ przypadku muszą zostać odczytane przez deterministyczny algorytm obliczający funkcję Na przykład, jeśli funkcja przyjmuje wartość 0, gdy wszystkie bity są równe 0, aw przeciwnym razie przyjmuje wartość 1 (jest to funkcja OR ), to jej deterministyczna złożoność zapytania wynosi dokładnie ${\ displaystyle n}$ . W najgorszym przypadku, niezależnie od $, w jakiej zdecyduje$ zbadać swoje dane wejściowe, wszystkie pierwsze odczytane bity mogą 0, a wartość funkcji zależy teraz od ostatniego bitu. Jeśli algorytm nie odczyta tego bitu, może wyświetlić nieprawidłową odpowiedź. (Takie argumenty nazywane są argumentami przeciwnika). Liczba odczytanych bitów jest również nazywana liczbą zapytań skierowanych do danych wejściowych. Można sobie wyobrazić, że algorytm pyta (lub pyta) dane wejściowe o określony bit, a dane wejściowe odpowiadają na to zapytanie.

Złożoność losowego zapytania oceny funkcji jest zdefiniowana podobnie, z wyjątkiem tego, że algorytm może być losowy. Innymi słowy, może rzucić monetą i wykorzystać wynik tych rzutów monetą, aby zdecydować, które bity mają zostać zapytane w jakiej kolejności. Jednak losowy algorytm nadal musi dawać poprawną odpowiedź dla wszystkich danych wejściowych: nie wolno popełniać błędów. Takie algorytmy nazywane są algorytmami Las Vegas . (Inna klasa algorytmów, algorytmy Monte Carlo , może popełnić pewien błąd.) Złożoność losowego zapytania można zdefiniować zarówno dla algorytmów Las Vegas, jak i Monte Carlo, ale losowa wersja hipotezy Aanderaa – Karpa – Rosenberga dotyczy Las Vegas Złożoność zapytań Vegas właściwości grafu.

Złożoność zapytań kwantowych jest naturalnym uogólnieniem losowej złożoności zapytań, oczywiście dopuszczając zapytania i odpowiedzi kwantowe. Złożoność zapytań kwantowych można również zdefiniować w odniesieniu do algorytmów Monte Carlo lub algorytmów Las Vegas, ale zwykle rozumie się przez to algorytmy kwantowe Monte Carlo.

W kontekście tego przypuszczenia funkcją do oceny jest właściwość wykresu, a dane wejściowe można traktować jako ciąg o rozmiarze ${\ Displaystyle n (n-1)/2}$ , opisując dla każdej pary wierzchołków, czy istnieje krawędź z tą parą jako punktami końcowymi. Złożoność zapytania dowolnej funkcji na tym wejściu jest co najwyżej ${\ displaystyle n (n-1)/2}$ , ponieważ algorytm, który sprawia, ${\ displaystyle n Zapytania (n-1)/2}$ mogą odczytać całe dane wejściowe i całkowicie określić graf wejściowy.

Deterministyczna złożoność zapytań

W przypadku algorytmów deterministycznych Rosenberg (1973) pierwotnie przypuszczał, że dla wszystkich nietrywialnych właściwości wykresu na $Ω$ podjęcie decyzji, czy wykres posiada tę właściwość, wymaga $\ Displaystyle \ Omega (n ^ {2}) }$ Warunek nietrywialności jest wyraźnie wymagany, ponieważ istnieją właściwości trywialne, takie jak „czy to jest wykres?” na które można odpowiedzieć bez żadnych pytań.

Wykres skorpiona. Jeden z trzech czerwonych wierzchołków ścieżki sąsiaduje ze wszystkimi innymi wierzchołkami, a pozostałe dwa czerwone wierzchołki nie mają żadnych innych przylegań.

$wykazywał właściwość$ skierowanego (właściwość zawierania „ujścia”), która wymagała tylko zapytań do Zlew na grafie skierowanym $jest$ wierzchołkiem stopnia wejściowego zewnętrznego zero Istnienie zlewu można przetestować za pomocą mniej niż $Best$ , van Emde Boas i Lenstra 1974 ). Nieskierowana właściwość wykresu, którą można również przetestować za pomocą $,$ jest właściwością bycia wykresem skorpiona, po raz pierwszy opisaną w , Emde Boas & Lenstra (1974 Graf skorpionowy to graf zawierający ścieżkę składającą się z trzech wierzchołków, tak że jeden koniec ścieżki jest połączony ze wszystkimi pozostałymi wierzchołkami, podczas gdy pozostałe dwa wierzchołki ścieżki nie mają krawędzi incydentnych innych niż te na ścieżce.

$,$ i Rosenberg sformułowali nowe przypuszczenie ( przypuszczenie Aanderaa-Rosenberga ) mówi, że rozstrzygnięcie, czy wykres posiada nietrywialną właściwość grafu monotonicznego wymaga . To przypuszczenie $pokazując,$ rozwiązane przez Rivesta i Vuillemina (1975) że co najmniej potrzebne do przetestowania dowolnej nietrywialnej właściwości wykresu monotonicznego . Granica została dodatkowo poprawiona ${1} {4}} - \ varepsilon {\ bigr)} n ^ {2}}$ Kleitmana i Kwiatkowskiego (1980 $2$ do ${$$($ dla dowolnego autorstwa Kahna, Saksa i Sturtevanta (1984 ) , do ${\ Displaystyle {\ bigl (}{\ tfrac {8} {25}} - \ varepsilon {\ bigr)} n ^ {2}}$ przez Korneffel & Triesch (2010) i do ${\ Displaystyle {\ bigl (}{\ tfrac {1} {3}} - \ varepsilon {\ bigr)} n ^ {2}}$ przez Scheidweiler & Triesch (2013) .

Richard Karp przypuszczał silniejsze stwierdzenie (które jest obecnie nazywane hipotezą wymijającą lub hipotezą Aanderaa – Karpa – Rosenberga ), że „każda nietrywialna właściwość wykresu monotonicznego dla grafów na $jest$ wymijająca”. Właściwość nazywana jest $czasami$ jeśli dany wykres ma tę właściwość, zapytań To przypuszczenie mówi, że najlepszy algorytm do testowania dowolnej nietrywialnej właściwości monotonicznej musi (w najgorszym przypadku) badać wszystkie możliwe krawędzie. To przypuszczenie jest nadal otwarte, chociaż kilka specjalnych właściwości wykresu okazało się wymijających $dla$ . Przypuszczenie zostało rozwiązane dla przypadku, w którym $jest$ , Saks i Sturtevant (1984) potęgą pierwszą , stosując podejście topologiczne . Hipoteza została również rozwiązana dla wszystkich nietrywialnych właściwości monotonicznych na grafach dwudzielnych przez Yao (1988) . Wykazano również $, że właściwości$ drugorzędne -zamknięte są wymijające dla dużych Chakrabarti , Khot i Shi 2001 ).

W Kahn, Saks & Sturtevant (1984) przypuszczenie zostało uogólnione również na właściwości innych (niegraficznych) funkcji, przypuszczając, że każda nietrywialna funkcja monotoniczna, która jest słabo symetryczna, jest wymijająca. Ten przypadek jest również rozwiązany, gdy jest potęgą pierwszą $Lovász$ Young (2002) .

Randomizowana złożoność zapytań

$,$ że zapytania są wymagane do testowania nietrywialnych właściwości monotonicznych, nawet jeśli $niż$ jednostajna właściwość, która wymaga mniej . Liniowa dolna granica (tj . $właściwości$ monotonicznych wynika z bardzo ogólnego między złożonością zapytań losowych i deterministycznych Pierwsza superliniowa dolna granica dla wszystkich właściwości monotonicznych została podana przez Yao (1991) , który wykazał, że ${\ Displaystyle \ Omega {\ bigl (} n (\ log n) ^ {1 /12}{\bigr )}}$ zapytania są wymagane. Zostało to dodatkowo ulepszone przez $Displaystyle \ Omega (n ^$ 1991) do , a następnie przez Hajnala (1991) ( $styl wyświetlania \Omega (n^{4/3})}$ . $\$ Zostało to następnie ulepszone do obecnie najlepiej znanej dolnej granicy (wśród granic, które obowiązują dla wszystkich właściwości monotonicznych) ${\ Displaystyle \ Omega {\ bigl (} n ^ { 4/3}(\log n)^{1/3}{\bigr )}}$ autorstwa Chakrabarti & Khot (2007) .

Niektóre ostatnie wyniki dają dolne granice, które są określone przez prawdopodobieństwo krytyczne $właściwości$ wykresu monotonicznego. Prawdopodobieństwo krytyczne $0,1$ się jako unikalną liczbę $\ Displaystyle [$ zakresie $]}$ taką, że losowy wykres ${\ displaystyle G (n, p)}$ (uzyskany przez losowe wybranie, czy każda krawędź istnieje, niezależnie od innych krawędzi, z prawdopodobieństwem na krawędź) posiada tę właściwość z prawdopodobieństwem równym $displaystyle$${\ tfrac {1}{2}}}$ . Friedgut, Kahn i Wigderson (2002) wykazali, że każda jednostajna właściwość z krytycznym prawdopodobieństwem wymaga ${\ displaystyle p}$

$${\ Displaystyle \ Omega \ lewo (\ min \ lewo \ {{\ Frac {n}} {\ min (p, 1-p )}},{\frac {n^{2}}{\log n}}\prawo\}\prawo)}$$

zapytania. W przypadku tego samego problemu O'Donnell i in. (2005) wykazał dolną granicę ${\ Displaystyle \ Omega (n ^ {4/3} / p ^ {1/3})}$ .

$których$ w przypadku deterministycznym, istnieje wiele specjalnych właściwości, dla dolna Ponadto znane są lepsze dolne granice dla kilku klas właściwości grafu. Na przykład, aby sprawdzić, czy graf ma podgraf izomorficzny z dowolnym danym wykresem (tak zwany izomorfizmu podgrafu ), najlepiej znaną dolną granicą jest ${\ Displaystyle \ Omega (n ^ {3/ 2})}$ dzięki Grögerowi (1992) .

Złożoność zapytań kwantowych

złożoności zapytań kwantowych z ograniczonym błędem najlepiej znaną dolną granicą jest ${\ Displaystyle \ Omega {\ bigl (} n ^ {2/3} (\ log n )^{1/6}{\bigr )}}$ jak zauważył Andrew Yao. Uzyskuje się go przez połączenie losowej dolnej granicy z kwantową metodą przeciwnika. ${\ Displaystyle O (n$ jaką można osiągnąć, to $,$ w przeciwieństwie do klasycznego przypadku, ze względu na algorytm Grovera , który daje } algorytm zapytań do testowania monotonicznej właściwości niepustości. Podobnie jak w przypadku deterministycznym i losowym, istnieją pewne właściwości, o których wiadomo, że mają dolną granicę, na przykład brak pustki (co wynika z optymalności algorytmu Grovera) i ${\ Displaystyle \ Omega (n) }$ właściwość zawierania trójkąta . Istnieją pewne właściwości wykresu, o których wiadomo, że mają $)$$\Omega (n^{2})}$ niektóre właściwości z dolną $\$ dolna granica. Na przykład właściwość monotoniczności nieplanarności wymaga $a$ Ambainis i in. 2008 więcej niż połowę możliwych liczba krawędzi $in$ także funkcją większości) wymaga Beals . 2001 ).

Notatki

•    Ambainis, Andris ; Iwama, Kazuo ; Nakanishi, Masaki; Nishimura, Harumichi; Raymond, Rudy; Tani, Seiichiro; Yamashita, Shigeru (2008), „Złożoność zapytań kwantowych funkcji boolowskich z małymi zestawami”, w: Hong, Seok-Hee ; Nagamochi, Hiroshi; Fukunaga, Takuro (red.), Materiały z 19. Międzynarodowego Sympozjum Algorytmów i Obliczeń (ISAAC 2008) , Notatki z wykładów z informatyki , tom. 5369, Springer-Verlag , s. 907–918, doi : 10.1007/978-3-540-92182-0_79 , ISBN 978-3-540-92181-3 , MR 2539981
•   Beals, Robert; Buhrman, Harry; Kleve, Richard ; Mosca, Michele ; de Wolf, Ronald (2001), „Dolne granice kwantowe przez wielomiany”, Journal of the ACM , 48 (4): 778–797, arXiv : quant-ph/9802049 , doi : 10,1145/502090,502097 , MR 2144930
• Najlepszy, panie; van Emde Boas, P .; Lenstra, HW (1974), Zaostrzona wersja hipotezy Aanderaa-Rosenberga , Raport ZW 30/74, Mathematisch Centrum Amsterdam , hdl : 1887/3792
•   Chakrabarti, Amit; Khot, Subhash (2007), „Ulepszone dolne granice losowej złożoności właściwości wykresu”, Random Structures & Algorithms , 30 (3): 427–440, doi : 10,1002 / rsa.20164 , MR 2309625
•    Chakrabarti, Amit; Chot, Subhash ; Shi, Yaoyun (2001), „Unikanie zawierania podgrafów i właściwości pokrewnych”, SIAM Journal on Computing , 31 (3): 866–875, CiteSeerX 10.1.1.29.3131 , doi : 10.1137/S0097539700382005 , MR 1896462
•   Friedgut, Ehud; Kahn, Jeff; Wigderson, Avi (2002), „Obliczanie właściwości wykresu według losowych partycji podsześcianu”, w: Rolim, José DP; Vadhan, Salil (red.), Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2002) , Lecture Notes in Computer Science , tom. 2483, Springer-Verlag , s. 105–113, doi : 10.1007/3-540-45726-7_9 , ISBN 978-3-540-44147-2
•   Gröger, Hans Dietmar (1992), „O losowej złożoności właściwości wykresu monotonicznego” (PDF) , Acta Cybernetica , 10 (3): 119–127, MR 1206981
•  ${\ Displaystyle \ Omega (n ^ {4/3})} dolna$ ), "An losowej złożoności właściwości wykresu", Combinatorica , 11 (2): 131 –143, doi : 10.1007/BF01206357 , MR 1136162
•   Kahn, Jeff; Saks, Michał ; Sturtevant, Dean (1984), „topologiczne podejście do unikania”, Combinatorica , 4 (4): 297–306, doi : 10.1007 / BF02579140 , MR 0779890
•  ${\ Displaystyle \ Omega (n ^ {5/4})}$ , Valerie (1991), „An dolna granica losowej złożoności właściwości wykresu”, , 11 ( 1): 23 –32, doi : 10.1007/BF01375470 , MR 1112271
• Kleitman, DJ ; Kwiatkowski, DJ (1980), „Dalsze wyniki hipotezy Aanderaa-Rosenberga”, Journal of Combinatorial Theory, Series B , 28 : 85–95, doi : 10.1016/0095-8956 (80) 90057-X
•   Kozlov, Dmitry (2008), kombinatoryczna topologia algebraiczna , Springer-Verlag, ISBN 978-3-540-73051-4
• Lutz, Frank H. (2001), „Niektóre wyniki związane z hipotezą unikania”, Journal of Combinatorial Theory , Seria B , 81 (1): 110–124, doi : 10.1006 / jctb.2000.2000
• Korneffel, Torsten; Triesch, Eberhard (2010), „Asymptotyczna granica złożoności właściwości wykresu monotonicznego”, Combinatorica , Springer-Verlag, 30 (6): 735–743, doi : 10.1007 / s00493-010-2485-3
• Magniez, Fryderyk; Santha, Miklos; Szegedy, Mario (2005), „Algorytmy kwantowe dla problemu trójkąta”, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) , Vancouver, British Columbia: Society for Industrial and Applied Mathematics , s. 1109–1117 , arXiv : quant-ph/0310134 , Bibcode : 2003quant.ph.10134M
•   O'Donnell, Ryan; Saks, Michał ; Schramm, Oded ; Servedio, Rocco A. (2005), „Każde drzewo decyzyjne ma wpływową zmienną”, Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005) , s. 31–39, arXiv : cs / 0508071 , doi : 10.1109 /SFCS.2005.34 , ISBN 978-0-7695-2468-9
•   Rivest, Ronald L .; Vuillemin, Jean (1975), „Uogólnienie i dowód hipotezy Aanderaa-Rosenberga”, Proceedings of the 7th ACM Symposium on Theory of Computing (STOC 1975) , Albuquerque, Nowy Meksyk, Stany Zjednoczone, s. 6–11, CiteSeerX 10.1.1.309.7236 , doi : 10.1145/800116.803747
• Rosenberg, Arnold L. (1973), „O czasie wymaganym do rozpoznania właściwości grafów: problem”, SIGACT News , 5 (4): 15–16, doi : 10.1145/1008299.1008302
• Scheidweiler, Robert; Triesch, Eberhard (2013), „Dolna granica złożoności właściwości wykresu monotonicznego”, SIAM Journal on Discrete Mathematics , 27 (1): 257–265, doi : 10,1137/120888703
• Triesch, Eberhard (1996), „O złożoności rozpoznawania niektórych właściwości wykresu”, Combinatorica , 16 (2): 259–268, doi : 10.1007 / BF01844851
• Yao, Andrew Chi-Chih (1988), „Właściwości monotonicznego wykresu dwudzielnego są wymijające”, SIAM Journal on Computing , 17 (3): 517–520, doi : 10,1137/0217031
• Yao, Andrew Chi-Chih (1991), „Dolne granice losowych algorytmów dla właściwości grafów”, Journal of Computer and System Sciences , 42 (3): 267–287, doi : 10.1016 / 0022-0000 (91) 90003-N

Dalsza lektura

•   Bollobás, Béla (2004), „Rozdział VIII. Złożoność i pakowanie”, Extreme Graph Theory , Nowy Jork: Dover Publications , s. 401–437, ISBN 978-0-486-43596-1 .
• Lovász, László ; Young, Neal E. (2002), „Notatki z wykładu na temat unikalności właściwości wykresu”, arXiv : cs / 0205031v1
•   Chronaki, Catherine E (1990), Badanie unikalności: dolne granice złożoności drzew decyzyjnych funkcji boolowskich , CiteSeerX 10.1.1.37.1041 .
• Michael Saks , Drzewa decyzyjne: problemy i wyniki, stare i nowe (PDF)