Beslutsträdmodell

I beräkningskomplexitet är beslutsträdsmodellen beräkningsmodellen där en algoritm i grunden anses vara ett beslutsträd , dvs en sekvens av frågor eller tester som görs adaptivt, så att resultatet av tidigare tester kan påverka de tester som utförs nästa .

Vanligtvis har dessa test ett litet antal utfall (som en ja–nej-fråga ) och kan utföras snabbt (säg, med enhetsberäkningskostnad), så den värsta tänkbara tidskomplexiteten för en algoritm i beslutsträdsmodellen motsvarar djupet på motsvarande beslutsträd. Denna uppfattning om beräkningskomplexitet för ett problem eller en algoritm i beslutsträdsmodellen kallas dess beslutsträdskomplexitet eller frågekomplexitet .

Beslutsträdsmodeller är avgörande för att fastställa lägre gränser för komplexitetsteori för vissa klasser av beräkningsproblem och algoritmer. Flera varianter av beslutsträdsmodeller har introducerats, beroende på vilken beräkningsmodell och vilken typ av frågealgoritmer som tillåts utföra.

Till exempel används ett beslutsträdargument för att visa att en jämförelsesort av $n$ poster måste ta $n\log(n)$ jämförelser. För jämförelsesorter är en fråga en jämförelse av två objekt $a,\,b$ , med två utfall (förutsatt att inga objekt är lika): antingen $a<b$ eller $a>b$ . Jämförelsesorteringar kan uttryckas som ett beslutsträd i denna modell, eftersom sådana sorteringsalgoritmer endast utför dessa typer av frågor.

Jämförelseträd och nedre gränser för sortering

Beslutsträd används ofta för att förstå algoritmer för sortering och andra liknande problem; detta gjordes först av Ford och Johnson.

Till exempel är många sorteringsalgoritmer jämförelsesorteringar , vilket innebär att de bara får information om en inmatningssekvens $x_{1},x_{2},\ldots ,x_{n }$ via lokala jämförelser: testar om $x_{i}<x_{j}$ , $x_{i}=x_{j}$ eller $x_{i}>x_{j}$ . Om vi antar att alla objekt som ska sorteras är distinkta och jämförbara, kan detta omformuleras som en ja-eller-nej-fråga: är $x_{i}>x_{j}$ ?

Dessa algoritmer kan modelleras som binära beslutsträd, där frågorna är jämförelser: en intern nod motsvarar en fråga, och nodens barn motsvarar nästa fråga när svaret på frågan är ja eller nej. För bladnoder motsvarar utmatningen en permutation $\pi$ som beskriver hur inmatningssekvensen förvrängdes från den fullständigt ordnade listan med objekt. (Inversen av denna permutation, $\pi ^{-1}$ , omordnar inmatningssekvensen.)

Man kan visa att jämförelsesorter måste använda $\Omega (n\log(n))$ jämförelser genom ett enkelt argument: för att en algoritm ska vara korrekt måste den kunna mata ut varje möjlig permutation av $n$ element; annars skulle algoritmen misslyckas för just den permutationen som indata. Så dess motsvarande beslutsträd måste ha minst lika många löv som permutationer: $n!$ lämnar. Vilket binärt träd som helst med minst $n!$ blad har djup minst $\log _{2}(n!)=\Omega (n\log _ {2}(n))$ , så detta är en nedre gräns för körtiden för en jämförelsesorteringsalgoritm. I det här fallet visar förekomsten av många jämförelsesorteringsalgoritmer med denna tidskomplexitet, såsom mergesort och heapsort , att gränsen är snäv.

Detta argument använder inget om typen av fråga, så det bevisar faktiskt en nedre gräns för alla sorteringsalgoritmer som kan modelleras som ett binärt beslutsträd. I huvudsak är detta en omformulering av det informationsteoretiska argumentet att en korrekt sorteringsalgoritm måste lära sig åtminstone $\log _{2}(n!)$ informationsbitar om inmatningssekvensen . Som ett resultat fungerar detta även för randomiserade beslutsträd.

Andra nedre gränser för beslutsträd använder att frågan är en jämförelse. Tänk till exempel på uppgiften att endast använda jämförelser för att hitta det minsta talet bland $n$ tal. Innan det minsta talet kan bestämmas måste varje nummer utom det minsta "förlora" (jämföra större) i minst en jämförelse. Så det krävs minst $n-1$ jämförelser för att hitta minimum. (Det informationsteoretiska argumentet här ger bara en nedre gräns för ${\displaystyle \log(n)} .$ ) Ett liknande argument fungerar för allmänna nedre gränser för beräkningsordningsstatistik .

Linjära och algebraiska beslutsträd

Linjära beslutsträd generaliserar ovanstående jämförelsebeslutsträd till beräkningsfunktioner som tar reella vektorer $x\in \mathbb {R} ^{n}$ som indata. Testerna i linjära beslutsträd är linjära funktioner: för ett särskilt val av reella tal $a_{0},\dots ,a_{n}$ mata ut tecknet för $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ . (Algorithmer i den här modellen kan bara bero på utsignalens tecken.) Jämförelseträd är linjära beslutsträd, eftersom jämförelsen mellan $x_{i}$ och $x_{j}$ motsvarar den linjära funktionen $x_{i}-x_{j}$ . Från dess definition kan linjära beslutsträd endast specificera funktioner $f$ vars fibrer kan konstrueras genom att ta fackföreningar och skärningar av halvrum.

Algebraiska beslutsträd är en generalisering av linjära beslutsträd som tillåter testfunktionerna att vara polynom av graden $d$ . Geometriskt är utrymmet uppdelat i semi-algebraiska uppsättningar (en generalisering av hyperplan).

Dessa beslutsträdsmodeller, definierade av Rabin och Reingold, används ofta för att bevisa lägre gränser i beräkningsgeometri . Till exempel visade Ben-Or att elementets unikhet (uppgiften att beräkna ${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}} ,$ där $f(x)$ är 0 om och endast om det finns distinkta koordinater $i,j$ så att $x_{i}=x_{j }$ ) kräver ett algebraiskt beslutsträd med djup $\Omega (n\log(n))$ . Detta visades först för linjära beslutsmodeller av Dobkin och Lipton. De visar också en $n^{2}$ nedre gräns för linjära beslutsträd på ryggsäcksproblemet, generaliserade till algebraiska beslutsträd av Steele och Yao.

Booleska beslutsträdskomplexiteter

För booleska beslutsträd är uppgiften att beräkna värdet av en n-bitars boolesk funktion $f:\{0,1\}^{n}\to \ {0,1\}$ för en ingång $x\in \{0,1\}^{n}$ . Frågorna motsvarar att läsa en bit av indata, $x_{i}$ , och utdata är $f(x)$ . Varje fråga kan vara beroende av tidigare frågor. Det finns många typer av beräkningsmodeller som använder beslutsträd som kan övervägas, som tillåter flera komplexitetsuppfattningar, kallade komplexitetsmått .

Deterministiskt beslutsträd

Om utdata från ett beslutsträd är $f(x)$ , för alla $x\in \{0,1\}^{n}$ , beslutsträdet sägs "beräkna" $f$ . Djupet på ett träd är det maximala antalet frågor som kan hända innan ett löv nås och ett resultat erhålls. $D(f)$ , det deterministiska beslutsträdets komplexitet för $f$ är det minsta djupet bland alla deterministiska beslutsträd som beräknar $f$ .

Randomiserat beslutsträd

Ett sätt att definiera ett randomiserat beslutsträd är att lägga till ytterligare noder till trädet, var och en styrd av en sannolikhet $p_{i}$ . En annan likvärdig definition är att definiera det som en fördelning över deterministiska beslutsträd. Baserat på denna andra definition definieras komplexiteten hos det randomiserade trädet som det största djupet bland alla träden till stöd för den underliggande fördelningen. $R_{2}(f)$ definieras som komplexiteten hos det randomiserade beslutsträdet med lägsta djup vars resultat är $f(x)$ med sannolikhet minst $2/3$ för alla $x\in \{0,1\}^{n}$ (dvs. med begränsat 2-sidigt fel).

$R_{2}(f)$ är känd som Monte Carlos randomiserade beslutsträdskomplexitet, eftersom resultatet tillåts vara felaktigt med avgränsat dubbelsidigt fel. Las Vegas beslutsträdskomplexitet $R_{0}(f)$ mäter det förväntade djupet av ett beslutsträd som måste vara korrekt (dvs. har nollfel). Det finns också en enkelsidig bounded-error-version som betecknas med $R_{1}(f)$ .

Icketerministiskt beslutsträd

Den icke-deterministiska beslutsträdskomplexiteten för en funktion är mer känd som certifikatkomplexiteten för den funktionen. Den mäter antalet inmatade bitar som en icke-deterministisk algoritm skulle behöva titta på för att utvärdera funktionen med säkerhet.

Formellt är certifikatkomplexiteten för $f$ vid $x$ storleken på den minsta delmängden av index $S\subset [n]$ så att, för alla $y\in \{0,1\}^{n}$ , om $y_{i}=x_{i}$ för alla ${\ displaystyle i\in S}$ , sedan $f(y)=f(x)$ . Certifikatkomplexiteten för $f$ är den maximala certifikatkomplexiteten över alla $x$ . Den analoga föreställningen där man bara kräver att verifieraren är korrekt med 2/3 sannolikhet betecknas $RC(f)$ .

Kvantbeslutsträd

Kvantbeslutsträdets komplexitet $Q_{2}(f)$ är djupet av det kvantbeslutsträd med lägsta djup som ger resultatet $f(x)$ med sannolikhet minst $2/3$ alla $x\in \{0,1\}^{n$ . En annan storhet, $Q_{E}(f)$ , definieras som djupet av kvantbeslutsträdet med lägsta djup som ger resultatet $f(x)$ med sannolikhet 1 i alla fall (dvs. beräknar $f$ exakt). $Q_{2}(f)$ och $Q_{E}(f)$ är mer kända som kvantfrågekomplexiteter , eftersom den direkta definitionen av ett kvantbeslut träd är mer komplicerat än i det klassiska fallet. I likhet med det randomiserade fallet definierar vi $Q_{0}(f)$ och $Q_{1}(f)$ .

Dessa begrepp är vanligtvis avgränsade av begreppen grad och ungefärlig grad. Graden av $f$ , betecknad $\deg(f)$ , är den minsta graden av ett polynom $p$ som uppfyller $f(x)=p(x)$ för alla $x\in \{0,1\}^{n}$ . Den ungefärliga graden av $f$ , betecknad ${\widetilde {\deg }}(f)$ , är den minsta graden av ett polynom $p$ som uppfyller $p(x)\in [0,1/3]$ när $f(x)=0$ och $p(x)\in [2/3,1]$ när $f(x)=1$ .

Beals et al. fastställt att $Q_{0}(f)\geq \deg(f)/2$ och ${\ displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$ .

Samband mellan booleska funktionskomplexitetsmått

$Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ följer omedelbart av definitionerna att för alla $n$ -bitars booleska funktioner $f$ , och $Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$ . Att hitta de bästa övre gränserna i den omvända riktningen är ett viktigt mål när det gäller frågekomplexitet.

Alla dessa typer av frågekomplexitet är polynomiellt relaterade. Blum och Impagliazzo, Hartmanis och Hemachandra och Tardos upptäckte oberoende att $D(f)\leq R_{0}(f)^{2}$ . Noam Nisan fann att Monte Carlos randomiserade beslutsträdskomplexitet också är polynomiellt relaterad till deterministisk beslutsträdskomplexitet: $D(f)=O(R_{2}( f)^{3})$ . (Nisan visade också att ${\displaystyle D(f)=O(R_{1}(f)^{2})} .$ ) Ett snävare samband är känt mellan Monte Carlo och Las Vegas modellerna: $R_{0}(f)=O(R_{2}(f)^ {2}\log R_{2}(f))$ . Detta förhållande är optimalt upp till polylogaritmiska faktorer. När det gäller kvantbeslutsträdskomplexiteter, ${\displaystyle D(f)=O(Q_{2}(f)^{4})} ,$ och denna gräns är snäv . Midrijanis visade att ${\displaystyle D(f)=O(Q_{0}(f)^{3})} ,$ vilket förbättrade en kvartsbindning på grund av Beals et al.

Det är viktigt att notera att dessa polynomrelationer endast är giltiga för totala booleska funktioner. För partiella booleska funktioner $) {\displaystyle Q_{0}(f )}$ har en domän en delmängd av $\{0,1\}^{n}$ , en exponentiell separation mellan och $D(f)$ är möjlig; det första exemplet på ett sådant problem upptäcktes av Deutsch och Jozsa .

Känslighetsgissningar

För en boolesk funktion ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}},$ känsligheten för f $\displaystyle f}$ definieras som den maximala känsligheten för $f$ över alla $x$ , där känsligheten för $f$ vid $x$ är antalet enbitsändringar i $x$ som ändrar värdet på $f(x)$ . Känslighet är relaterad till begreppet total påverkan från analysen av booleska funktioner , vilket är lika med genomsnittlig känslighet över alla $x$ .

Känslighetsförmodan är gissningen att känslighet är polynomiellt relaterad till frågekomplexitet ; det vill säga det finns exponent $c,c'$ så att för alla $f$ , $D(f) =O(s(f)^{c})$ och $s(f)=O(D(f)^{c'})$ . Man kan visa genom ett enkelt argument att ${\displaystyle s(f)\leq D(f)} ,$ så gissningen är specifikt angelägen om att hitta en nedre gräns för känslighet. Eftersom alla de tidigare diskuterade komplexitetsmåtten är polynomiellt relaterade, är den exakta typen av komplexitetsmått inte relevant. Detta är dock vanligtvis formulerat som frågan om att relatera känslighet med blockkänslighet.

Blockkänsligheten för $f$ , betecknad $bs(f)$ , definieras som den maximala blockkänsligheten för $f$ över alla $x$ . Blockkänsligheten för $f$ vid $x$ är det maximala antalet $t$ av disjunkta delmängder $S_{1},\ ldots ,S_{t}\subset [n]$ så att, för någon av delmängderna ${\displaystyle S_{i}},$ vänder bitarna av $x$ motsvarande $S_{ i}$ ändrar värdet på $f(x)$ .

Eftersom blockkänslighet tar ett maximum över fler val av delmängder, $s(f)\leq bs(f)$ . Vidare är blockkänslighet polynomiellt relaterad till de tidigare diskuterade komplexitetsmåtten; till exempel, Nisans papper som introducerade blockkänslighet visade att $bs(f)\leq D(f)=O(bs(f) )^{4})$ . Så man skulle kunna formulera om känslighetsförmodan som att visa att för vissa $c$ , $bs(f)=O(s(f)^ {c})$ . 1992 antog Nisan och Szegedy att $c=2$ räcker. Detta skulle vara snävt, eftersom Rubinstein 1995 visade en kvadratisk separation mellan känslighet och blockkänslighet.

I juli 2019, 27 år efter att gissningen ursprungligen ställdes, bevisade Hao Huang från Emory University känslighetsförmodan, vilket visade att $bs(f)=O(s) (f)^{4})$ . Detta bevis är särskilt kortfattat och bevisar detta påstående på två sidor när tidigare framsteg mot känslighetsförmodan hade varit begränsade.

Sammanfattning av kända resultat

Mest kända separationer för komplexitetsmått från och med oktober 2020
	$D$	$R_{0}$	$R_{2}$	$C$	$\displaystyle RC}$	$bs$	$s$	$Q_{0}$	$\deg$	$Q$	$\displaystyle {\widetilde {\deg }}}$
$D$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
$R_{0}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
$R$	1	1		2	2, 3	2, 3	3, 6	1,5, 3	2, 3	3, 4	4
$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
$bs$	1	1	1	1	1		2, 4	1.15, 2	1,63, 2	2	2
$s$	1	1	1	1	1	1		1.15, 2	1,63, 2	2	2
$Q_{0}$	1	1,33, 2	1,33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
$\deg$	1	1,33, 2	1,33, 2	2	2	2	2	1		2	2
$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

Den här tabellen sammanfattar resultat för separationer mellan booleska funktionskomplexitetsmått. Komplexitetsmåtten är, i ordning, deterministiska, nollfel randomiserade, dubbelsidiga fel randomiserade, certifikat, randomiserade certifikat, blockkänslighet, känslighet, exakt kvantum, grad, kvant och ungefärlig grad komplexitet.

Numret i $A$ -th rad och $B$ -th kolumn anger gränser för exponenten $c$ , vilket är infimum av alla $k$ som uppfyller $A(f)=O(B(f)^{k})$ för alla booleska funktioner $f$ . Till exempel är posten i D:te raden och s:te kolumnen "3, 6", så $D(f) =O(\operatörsnamn {s} (f)^{6+o(1)})$ för alla $f$ , och det finns en funktion $g$ så att $D(g)=\Omega (\operatörsnamn {s} (g)^{3-o(1)})$ .

Se även

Undersökningar

Buhrman, Harry; de Wolf, Ronald (2002), "Complexity Measures and Decision Tree Complexity: A Survey" (PDF) , Theoretical Computer Science , 288 (1): 21–43, doi : 10.1016/S0304-3975(01)00144-X