Modelul arborelui decizional - Decision tree model

În complexitate de calcul modelul arbore de decizie este modelul de calcul în care un algoritm este considerat a fi în principiu , un arbore de decizie , și anume, o secvență de interogări sau teste care sunt efectuate în mod adaptiv, astfel încât rezultatele testelor anterioare pot influența testul este efectuat în continuare.

În mod obișnuit, aceste teste au un număr mic de rezultate (cum ar fi o întrebare da-nu) și pot fi efectuate rapid (să zicem, cu un cost de calcul unitar), astfel încât cea mai rea situație de timp a unui algoritm în modelul arborelui decizional corespunde adâncimea arborelui decizional corespunzător. Această noțiune de complexitate de calcul a unei probleme sau a unui algoritm în modelul arborelui decizional se numește complexitatea arborelui decizional sau complexitatea interogării .

Modelele de arbori de decizie sunt esențiale în stabilirea unor limite inferioare pentru teoria complexității pentru anumite clase de probleme de calcul și algoritmi. Au fost introduse mai multe variante ale modelelor arborelui decizional, în funcție de modelul de calcul și tipul de algoritmi de interogare care sunt permise să efectueze.

De exemplu, un argument al arborelui decizional este utilizat pentru a arăta că un tip de comparație a articolelor trebuie să facă comparații. Pentru tipuri de comparație, o interogare este o comparație a două articole , cu două rezultate (presupunând că niciun articol nu este egal): fie sau . Sortările de comparație pot fi exprimate ca un arbore de decizie în acest model, deoarece astfel de algoritmi de sortare efectuează numai aceste tipuri de interogări. ${\ displaystyle n}$${\ displaystyle n \ log (n)}$${\ displaystyle a, \, b}$${\ displaystyle a <b}$${\ displaystyle a> b}$

Arborii de comparație și limitele inferioare pentru sortare

Arborii de decizie sunt adesea folosiți pentru a înțelege algoritmii de sortare și alte probleme similare; acest lucru a fost făcut pentru prima dată de Ford și Johnson.

De exemplu, mulți algoritmi de sortare sunt soiuri de comparație , ceea ce înseamnă că acestea obține doar informații cu privire la o secvență de intrare prin comparatii locale: testarea dacă , sau . Presupunând că articolele care urmează a fi sortate sunt toate distincte și comparabile, acest lucru poate fi reformulat ca o întrebare da-sau-nu: este ? ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$${\ displaystyle x_ {i} <x_ {j}}$${\ displaystyle x_ {i} = x_ {j}}$${\ displaystyle x_ {i}> x_ {j}}$${\ displaystyle x_ {i}> x_ {j}}$

Acești algoritmi pot fi modelați ca arbori de decizie binari, unde interogările sunt comparații: un nod intern corespunde unei interogări, iar copiii nodului corespund următoarei interogări atunci când răspunsul la întrebare este da sau nu. Pentru nodurile frunze, ieșirea corespunde unei permutații care descrie modul în care secvența de intrare a fost criptată din lista complet ordonată de articole. (Inversul acestei permutări,, reordonează secvența de intrare.) ${\ displaystyle \ pi}$${\ displaystyle \ pi ^ {- 1}}$

Se poate arăta că tipurile de comparație trebuie să utilizeze comparații printr-un argument simplu: pentru ca un algoritm să fie corect, trebuie să fie capabil să producă fiecare permutare posibilă a elementelor; în caz contrar, algoritmul ar eșua pentru permutarea respectivă ca intrare. Deci, arborele său de decizie corespunzător trebuie să aibă cel puțin la fel de multe frunze ca permutări: frunze. Orice arbore binar cu cel puțin frunze are cel puțin adâncime , deci aceasta este o limită inferioară în timpul de execuție al unui algoritm de sortare a comparației. În acest caz, existența a numeroși algoritmi de sortare a comparației care au această complexitate de timp, cum ar fi mergesort și heapsort , demonstrează că legătura este strânsă. ${\ displaystyle \ Omega (n \ log (n))}$${\ displaystyle n}$${\ displaystyle n!}$${\ displaystyle n!}$${\ displaystyle \ log _ {2} (n!) = \ Omega (n \ log _ {2} (n))}$

Acest argument nu folosește nimic despre tipul de interogare, așa că, de fapt, dovedește o limită inferioară pentru orice algoritm de sortare care poate fi modelat ca un arbore de decizie binar. În esență, aceasta este o reformulare a argumentului teoretic al informației conform căruia un algoritm de sortare corect trebuie să învețe cel puțin biți de informații despre secvența de intrare. Ca rezultat, acest lucru funcționează și pentru arborii de decizie randomizați. ${\ displaystyle \ log _ {2} (n!)}$

Alte limite inferioare ale arborelui decizional folosesc că interogarea este o comparație. De exemplu, luați în considerare sarcina de a utiliza numai comparații pentru a găsi cel mai mic număr dintre numere. Înainte ca cel mai mic număr să poată fi determinat, fiecare număr, cu excepția celui mai mic, trebuie să „piardă” (compară mai mare) în cel puțin o comparație. Deci, este nevoie de cel puțin comparații pentru a găsi minimul. (Argumentul teoretic al informației de aici oferă doar o limită inferioară a .) Un argument similar funcționează pentru limite inferioare generale pentru statisticile ordinii de calcul . ${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle \ log (n)}$

Arborii de decizie liniari și algebrici

Arborii de decizie liniare generalizează arborii de decizie de comparație de mai sus la funcțiile de calcul care iau ca vectori reali intrare. Testele în arborii de decizie liniare sunt funcții liniare: pentru o anumită alegere a numerelor reale , se afișează semnul lui . (Algoritmii din acest model pot depinde doar de semnul ieșirii.) Arborii de comparație sunt arbori de decizie liniari, deoarece comparația dintre și corespunde funcției liniare . Din definiția sa, arborii de decizie liniari pot specifica doar funcții ale căror fibre pot fi construite luând uniuni și intersecții ale jumătăților de spații. ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$${\ displaystyle a_ {0}, \ dots, a_ {n}}$${\ displaystyle a_ {0} + \ textstyle \ sum _ {i = 1} ^ {n} a_ {i} x_ {i}}$${\ displaystyle x_ {i}}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {i} -x_ {j}}$${\ displaystyle f}$

Arborii de decizie algebrică sunt o generalizare a arborilor de decizie liniare care permit funcțiilor de testare să fie polinoame de grad . Geometric, spațiul este împărțit în mulțimi semi-algebrice (o generalizare a hiperplanului). ${\ displaystyle d}$

Aceste modele de arbori de decizie, definite de Rabin și Reingold, sunt adesea folosite pentru a demonstra limite inferioare în geometria de calcul . De exemplu, Ben-Or a arătat că unicitatea elementului (sarcina de calcul , unde este 0 dacă și numai dacă există coordonate distincte astfel încât ) necesită un arbore de decizie algebrică a adâncimii . Acest lucru a fost arătat pentru prima dată pentru modelele de decizie liniară de Dobkin și Lipton. Acestea arată, de asemenea, o limită inferioară pentru arborii de decizie liniari pe problema rucsacului, generalizată în arborii de decizie algebrică de Steele și Yao. ${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ {0,1 \}}$${\ displaystyle f (x)}$${\ displaystyle i, j}$${\ displaystyle x_ {i} = x_ {j}}$${\ displaystyle \ Omega (n \ log (n))}$${\ displaystyle n ^ {2}}$

Complexități arborescente de decizie booleene

Pentru arborii de decizie booleeni, sarcina este de a calcula valoarea unei funcții booleene n-biți pentru o intrare . Interogările corespund citirii unui pic din intrare , și ieșirea este . Fiecare interogare poate depinde de interogările anterioare. Există multe tipuri de modele de calcul care folosesc arborii de decizie care ar putea fi luați în considerare, acceptând noțiuni multiple de complexitate, numite măsuri de complexitate . ${\ displaystyle f: \ {0,1 \} ^ {n} \ to \ {0,1 \}}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle x_ {i}}$${\ displaystyle f (x)}$

Arborele de decizie determinist

Dacă rezultatul unui arbore de decizie este , pentru toate , arborele de decizie se spune că „calculează” . Adâncimea unui copac este numărul maxim de interogări care se pot întâmpla înainte de atingerea unei frunze și obținerea unui rezultat. , complexitatea arborelui de decizie determinist este cea mai mică adâncime dintre toți arborii de decizie deterministică care calculează . ${\ displaystyle f (x)}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle f}$${\ displaystyle D (f)}$${\ displaystyle f}$${\ displaystyle f}$

Arborele decizional aleatorizat

O modalitate de a defini un arbore de decizie randomizat este de a adăuga noduri suplimentare în arbore, fiecare controlat de o probabilitate . O altă definiție echivalentă este de a o defini ca o distribuție peste arbori de decizie deterministă. Pe baza acestei a doua definiții, complexitatea arborelui randomizat este definită ca fiind cea mai mare adâncime dintre toți arborii în sprijinul distribuției subiacente. este definit ca complexitatea arborelui de decizie randomizat cu cea mai mică adâncime al cărui rezultat este cu probabilitate cel puțin pentru toate (adică, cu o eroare față-verso mărginită). ${\ displaystyle p_ {i}}$${\ displaystyle R_ {2} (f)}$${\ displaystyle f (x)}$${\ displaystyle 2/3}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$

${\ displaystyle R_ {2} (f)}$este cunoscut sub numele de complexitatea randomizată a arborelui de decizie Monte Carlo , deoarece rezultatul este permis să fie incorect cu o eroare pe două fețe delimitată. Las Vegas Complexitatea-arbore de decizie măsoară de așteptat , adâncimea unui arbore de decizie care trebuie să fie corecte ( de exemplu, are eroare zero). Există, de asemenea, o versiune de eroare mărginită unilaterală care este notată cu . ${\ displaystyle R_ {0} (f)}$${\ displaystyle R_ {1} (f)}$

Arborele decizional nedeterminist

Complexitatea nedeterministă a arborelui decizional al unei funcții este cunoscută mai frecvent ca complexitatea certificatului acelei funcții. Măsoară numărul de biți de intrare la care ar trebui să analizeze un algoritm nedeterminist pentru a evalua funcția cu certitudine.

În mod formal, complexitatea certificatului at este de mărimea celui mai mic subset de indici, astfel încât, pentru toți , dacă pentru toți , atunci . Complexitatea certificatului este complexitatea maximă a certificatului . Se notează noțiunea analogică în care se cere doar verificatorului să fie corect cu probabilitate 2/3 . ${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle S \ subset [n]}$${\ displaystyle y \ in \ {0,1 \} ^ {n}}$${\ displaystyle y_ {i} = x_ {i}}$${\ displaystyle i \ in S}$${\ displaystyle f (y) = f (x)}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle RC (f)}$

Arborele decizional cuantic

Complexitatea arborelui decizional cuantic este adâncimea arborelui decizional cuantic cu cea mai mică adâncime care dă rezultatul cu probabilitate cel puțin pentru toate . O altă cantitate,, este definită ca adâncimea arborelui decizional cuantic cu cea mai mică adâncime care dă rezultatul cu probabilitatea 1 în toate cazurile (adică calculează exact). și sunt mai cunoscute sub denumirea de complexități de interogare cuantică , deoarece definiția directă a unui arbore decizional cuantic este mai complicată decât în ​​cazul clasic. Similar cu cazul randomizat, definim și . ${\ displaystyle Q_ {2} (f)}$${\ displaystyle f (x)}$${\ displaystyle 2/3}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle Q_ {E} (f)}$${\ displaystyle f (x)}$${\ displaystyle f}$${\ displaystyle Q_ {2} (f)}$${\ displaystyle Q_ {E} (f)}$${\ displaystyle Q_ {0} (f)}$${\ displaystyle Q_ {1} (f)}$

Aceste noțiuni sunt în mod obișnuit mărginite de noțiunile de grad și grad aproximativ. Gradul de , notat , este cel mai mic grad de orice polinom satisface pentru toți . Gradul aproximativ de , notat , este cel mai mic grad al oricărui polinom care satisface oricând și oricând . ${\ displaystyle f}$${\ displaystyle \ deg (f)}$${\ displaystyle p}$${\ displaystyle f (x) = p (x)}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle f}$${\ displaystyle {\ widetilde {\ deg}} (f)}$${\ displaystyle p}$${\ displaystyle p (x) \ în [0,1 / 3]}$${\ displaystyle f (x) = 0}$${\ displaystyle p (x) \ în [2 / 3,1]}$${\ displaystyle f (x) = 1}$

Beals și colab. a stabilit că și . ${\ displaystyle Q_ {0} (f) \ geq \ deg (f) / 2}$${\ displaystyle Q_ {2} (f) \ geq {\ widetilde {\ deg}} (f) / 2}$

Relațiile dintre măsurile complexității funcției booleene

Rezultă imediat din definițiile care pentru toate funcțiile booleene -bit , și . Găsirea celor mai bune limite superioare în direcția inversă este un obiectiv major în domeniul complexității interogărilor. ${\ displaystyle n}$${\ displaystyle f}$${\ displaystyle Q_ {2} (f) \ leq R_ {2} (f) \ leq R_ {1} (f) \ leq R_ {0} (f) \ leq D (f) \ leq n}$${\ displaystyle Q_ {2} (f) \ leq Q_ {0} (f) \ leq D (f) \ leq n}$

Toate aceste tipuri de complexitate a interogării sunt legate polinomial. Blum și Impagliazzo, Hartmanis și Hemachandra și Tardos au descoperit asta în mod independent . Noam Nisan a constatat că Monte Carlo randomizat complexitate arbore de decizie este , de asemenea , polinomial legată de decizie determinist copac complexitate: . (Nisan a arătat de asemenea că .) O relație mai strânsă este cunoscută între modelele Monte Carlo și Las Vegas: . Această relație este optimă până la factorii polilogaritmici. În ceea ce privește complexitatea arborelui decizional cuantic ,, și această legătură este strânsă. Midrijanis a arătat că , îmbunătățind o legătură quartică datorită lui Beals și colab. ${\ displaystyle D (f) \ leq R_ {0} (f) ^ {2}}$${\ displaystyle D (f) = O (R_ {2} (f) ^ {3})}$${\ displaystyle D (f) = O (R_ {1} (f) ^ {2})}$${\ displaystyle R_ {0} (f) = O (R_ {2} (f) ^ {2} \ log R_ {2} (f))}$${\ displaystyle D (f) = O (Q_ {2} (f) ^ {4})}$${\ displaystyle D (f) = O (Q_ {0} (f) ^ {3})}$

Este important să rețineți că aceste relații polinomiale sunt valabile numai pentru funcțiile booleene totale . Pentru funcțiile booleene parțiale , care au un domeniu dintr-un subset de , este posibilă o separare exponențială între și ; primul exemplu al unei astfel de probleme a fost descoperit de Deutsch și Jozsa . ${\ displaystyle \ {0,1 \} ^ {n}}$${\ displaystyle Q_ {0} (f)}$${\ displaystyle D (f)}$

Conjectura sensibilității

Pentru o funcție booleană , sensibilitatea de este definită ca fiind sensibilitatea maximă de peste tot , în cazul în care sensibilitatea la este numărul de modificări cu un singur bit în care schimbarea valorii . Sensibilitatea este legată de noțiunea de influență totală din analiza funcțiilor booleene , care este egală cu sensibilitatea medie asupra tuturor . ${\ displaystyle f: \ {0,1 \} ^ {n} \ to \ {0,1 \}}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle x}$

Conjectura Sensibilitatea este conjectura că sensibilitatea este polinomial legată de complexitatea interogare; adică există un exponent astfel încât, pentru toți , și . Se poate arăta printr-un argument simplu că , deci presupunerea este preocupată în mod specific de găsirea unei limite inferioare pentru sensibilitate. Deoarece toate măsurile de complexitate discutate anterior sunt legate polinomial, tipul precis de măsură de complexitate nu este relevant. Cu toate acestea, acest lucru este formulat în mod tipic ca problema legării sensibilității cu sensibilitatea la bloc. ${\ displaystyle c, c '}$${\ displaystyle f}$${\ displaystyle D (f) = O (s (f) ^ {c})}$${\ displaystyle s (f) = O (D (f) ^ {c '})}$${\ displaystyle s (f) \ leq D (f)}$

Sensibilitatea blocului de notat , este definită ca fiind sensibilitatea blocului maxim de peste tot . Sensibilitatea blocului de la at este numărul maxim de subseturi disjuncte astfel încât, pentru oricare dintre subseturi , întoarcerea biților corespunzătoare pentru modifică valoarea lui . ${\ displaystyle f}$${\ displaystyle bs (f)}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle t}$${\ displaystyle S_ {1}, \ ldots, S_ {t} \ subset [n]}$${\ displaystyle S_ {i}}$${\ displaystyle x}$${\ displaystyle S_ {i}}$${\ displaystyle f (x)}$

Deoarece sensibilitatea blocului necesită un maxim de mai multe opțiuni de subseturi ,. Mai mult, sensibilitatea la bloc este legată polinomial de măsurile de complexitate discutate anterior; de exemplu, lucrarea lui Nisan care introduce sensibilitatea la bloc a arătat că . Deci, s -ar putea reformula conjectura de sensibilitate ca arătând că, pentru unii , . În 1992, Nisan și Szegedy au presupus că este suficient. Acest lucru ar fi strâns, deoarece Rubinstein în 1995 a arătat o separare pătratică între sensibilitate și sensibilitate la bloc. ${\ displaystyle s (f) \ leq bs (f)}$${\ displaystyle bs (f) \ leq D (f) = O (bs (f) ^ {4})}$${\ displaystyle c}$${\ displaystyle bs (f) = O (s (f) ^ {c})}$${\ displaystyle c = 2}$

În iulie 2019, la 27 de ani după ce a fost inițial formulată conjectura, Hao Huang de la Universitatea Emory a dovedit conjectura sensibilității, arătând asta . Această dovadă este în special succintă, dovedind această afirmație în două pagini, când progresele anterioare către conjectura sensibilității fuseseră limitate. ${\ displaystyle bs (f) = O (s (f) ^ {4})}$

Rezumatul rezultatelor cunoscute

Cele mai cunoscute separări pentru măsurile de complexitate începând cu octombrie 2020

	${\ displaystyle D}$	${\ displaystyle R_ {0}}$	${\ displaystyle R_ {2}}$	${\ displaystyle C}$	${\ displaystyle RC}$	${\ displaystyle bs}$	${\ displaystyle s}$	${\ displaystyle Q_ {0}}$	${\ displaystyle \ deg}$	${\ displaystyle Q}$	${\ displaystyle {\ widetilde {\ deg}}}$
${\ displaystyle D}$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
${\ displaystyle R_ {0}}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
${\ displaystyle R}$	1	1		2	2, 3	2, 3	3, 6	1,5, 3	2, 3	3, 4	4
${\ displaystyle C}$	1	1	1, 2		2	2	2.22, 5	1.15, 3	1,63, 3	2, 4	2, 4
${\ displaystyle RC}$	1	1	1	1		1,5, 2	2, 4	1.15, 2	1,63, 2	2	2
${\ displaystyle bs}$	1	1	1	1	1		2, 4	1.15, 2	1,63, 2	2	2
${\ displaystyle s}$	1	1	1	1	1	1		1.15, 2	1,63, 2	2	2
${\ displaystyle Q_ {0}}$	1	1,33, 2	1,33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
${\ displaystyle \ deg}$	1	1,33, 2	1,33, 2	2	2	2	2	1		2	2
${\ displaystyle Q}$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\ displaystyle {\ widetilde {\ deg}}}$	1	1	1	2	2	2	2	1	1	1

Acest tabel rezumă rezultatele separărilor între măsurătorile complexității funcției booleene. Măsurile de complexitate sunt, în ordine, deterministe, eroare zero randomizată, eroare față-verso randomizată, certificat, certificat randomizat, sensibilitate bloc, sensibilitate, cuantică exactă, grad, cuantă și complexitate de grad aproximativ.

Numărul din al doilea rând și coloana-a desemnează limite ale exponentului , care este cel mai mic dintre toate satisfăcătoare pentru toate funcțiile booleene . De exemplu, intrarea în coloanele D-th și s-th este „3, 6”, deci pentru toți și există o funcție astfel încât . ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle c}$${\ displaystyle k}$${\ displaystyle A (f) = O (B (f) ^ {k})}$${\ displaystyle f}$${\ displaystyle D (f) = O (\ operatorname {s} (f) ^ {6 + o (1)})}$${\ displaystyle f}$${\ displaystyle g}$${\ displaystyle D (g) = \ Omega (\ operatorname {s} (g) ^ {3-o (1)})}$

Vezi si

• Sortare comparativă
• Arborele deciziei
• Conjectura Aanderaa – Karp – Rosenberg
• Arborele minim care se întinde # Arborii de decizie

Referințe

Sondaje

• Buhrman, Harry; de Wolf, Ronald (2002), „Măsuri de complexitate și complexitatea arborelui decizional: un sondaj” (PDF) , Informatică teoretică , 288 (1): 21–43, doi : 10.1016 / S0304-3975 (01) 00144-X