Beslutningstremodell - Decision tree model

I beregningskompleksitet den beslutningstre modellen er den modell for beregning i hvilken en algoritme er ansett for å være i hovedsak et beslutningstre , dvs. en sekvens av spørringer eller tester som er gjort adaptiv måte, slik at resultatet av de tidligere tester kan påvirke test er utført neste.

Vanligvis har disse testene et lite antall resultater (for eksempel et ja-nei-spørsmål) og kan utføres raskt (si med enhetsberegningskostnader), så den verste fallkompleksiteten til en algoritme i beslutningstreetmodellen tilsvarer dybden på det tilsvarende beslutningstreet. Denne forestillingen om beregningskompleksitet av et problem eller en algoritme i beslutningstre-modellen kalles beslutningstrekompleksitet eller spørringskompleksitet .

Beslutningstrærmodeller er medvirkende til å etablere lavere grenser for kompleksitetsteori for visse klasser av beregningsproblemer og algoritmer. Flere varianter av beslutningstremodeller har blitt introdusert, avhengig av beregningsmodellen og typen spørringsalgoritmer som får lov til å utføre.

For eksempel er et beslutningstre argument som brukes for å vise at en sammenligning slags av elementene må ta sammenligninger. For sammenligningssortering er en spørring en sammenligning av to elementer , med to resultater (forutsatt at ingen elementer er like): enten eller . Sammenligningssortering kan uttrykkes som et beslutningstreet i denne modellen, siden slike sorteringsalgoritmer bare utfører disse typer spørsmål. ${\ displaystyle n}$${\ displaystyle n \ log (n)}$${\ displaystyle a, \, b}$${\ displaystyle a <b}$${\ displaystyle a> b}$

Sammenligningstrær og nedre grenser for sortering

Beslutningstrær brukes ofte for å forstå algoritmer for sortering og andre lignende problemer; dette ble først gjort av Ford og Johnson.

For eksempel er mange sorterings algoritmer er sammenlignings slags , hvilket betyr at de bare få informasjon om en inngangssekvens via lokale sammenligninger: teste om , eller . Forutsatt at varene som skal sorteres er forskjellige og sammenlignbare, kan dette omformuleres som et ja-eller-nei-spørsmål: er det ? ${\ 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}}$

Disse algoritmene kan modelleres som binære beslutningstrær, der spørringene er sammenligninger: en intern node tilsvarer et spørsmål, og nodens barn tilsvarer neste spørsmål når svaret på spørsmålet er ja eller nei. For bladnoder tilsvarer utgangen en permutasjon som beskriver hvordan inngangssekvensen ble kryptert fra den fullordnede listen over varer. (Det omvendte av denne permutasjonen, ombestiller inngangssekvensen.) ${\ displaystyle \ pi}$${\ displaystyle \ pi ^ {- 1}}$

Man kan vise at sammenligningssortering må bruke sammenligninger gjennom et enkelt argument: for at en algoritme skal være korrekt, må den kunne sende ut alle mulige permutasjoner av elementer; Ellers ville algoritmen mislykkes for den spesielle permutasjonen som inngang. Så det tilhørende beslutningstreet må ha minst like mange blader som permutasjoner: blader. Ethvert binært tre med minst blader har minst dybde , så dette er en nedre grense på kjøretiden til en sammenligningssorteringsalgoritme. I dette tilfellet viser eksistensen av en rekke sammenligningssorteringsalgoritmer som har denne tidskompleksiteten, som fusjonssortering og høysort , at grensen er stram. ${\ displaystyle \ Omega (n \ log (n))}$${\ displaystyle n}$${\ displaystyle n!}$${\ displaystyle n!}$${\ displaystyle \ log _ {2} (n!) = \ Omega (n \ log _ {2} (n))}$

Dette argumentet bruker ikke noe om spørringstypen, så det viser faktisk en nedre grense for enhver sorteringsalgoritme som kan modelleres som et binært beslutningstreet. I hovedsak er dette en omformulering av det informasjonsteoretiske argumentet om at en riktig sorteringsalgoritme må lære minst informasjonsbiter om inngangssekvensen. Som et resultat fungerer dette også for randomiserte beslutningstrær. ${\ displaystyle \ log _ {2} (n!)}$

Andre beslutningstreet lavere grenser bruker at spørringen er en sammenligning. Vurder for eksempel oppgaven med å bare bruke sammenligninger for å finne det minste tallet blant tallene. Før det minste tallet kan bestemmes, må hvert tall unntatt det minste "miste" (sammenlign større) i minst en sammenligning. Så det tar i det minste sammenligninger for å finne minimum. (Informasjonen-teoretiske argument her bare gir en nedre grense av .) En lignende argument som fungerer for generelle nedre grenser for databehandling ordens statistikk . ${\ displaystyle n}$${\ displaystyle n-1}$${\ displaystyle \ log (n)}$

Lineære og algebraiske beslutningstrær

Lineære beslutningstrær generaliserer ovennevnte sammenligningstrær til databehandlingsfunksjoner som tar reelle vektorer som input. Testene i lineære beslutningstrær er lineære funksjoner: for et bestemt valg av reelle tall , skriv ut tegnet på . (Algoritmer i denne modellen kan bare avhenge av tegnet på utdataene.) Sammenligningstrær er lineære beslutningstrær, fordi sammenligningen mellom og tilsvarer den lineære funksjonen . Fra definisjonen kan lineære beslutningstrær bare spesifisere funksjoner hvis fibre kan konstrueres ved å ta fagforeninger og skjæringspunkter mellom halvrom. ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$${\ displaystyle a_ {0}, \ prikker, 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}$

Algebraiske beslutningstrær er en generalisering av lineære beslutningstrær som gjør at testfunksjonene kan være polynomer av grad . Geometrisk er rommet delt inn i semi-algebraiske sett (en generalisering av hyperplan). ${\ displaystyle d}$

Disse beslutningstre-modellene, definert av Rabin og Reingold, brukes ofte til å bevise lavere grenser i beregningsgeometri . For eksempel viste Ben-Or at elementets unikhet (databehandlingsoppgaven , hvor er 0 hvis og bare hvis det finnes forskjellige koordinater slik at ) krever et algebraisk beslutningstreet av dybden . Dette ble først vist for lineære beslutningsmodeller av Dobkin og Lipton. De viser også en nedre grense for lineære beslutningstrær på ryggsekkproblemet, generalisert til algebraiske beslutningstrær av Steele og 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}}$

Boolsk beslutningstreet kompleksitet

For boolske beslutningstrær er oppgaven å beregne verdien av en n-bit boolsk funksjon for en inngang . Spørringene tilsvarer å lese litt av inndataene , og utdataene er . Hver spørring kan være avhengig av tidligere spørsmål. Det er mange typer beregningsmodeller som bruker beslutningstrær som kan vurderes, og innrømmer flere kompleksitetsoppfatninger, kalt kompleksitetsmål . ${\ displaystyle f: \ {0,1 \} ^ {n} \ to \ {0,1 \}}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle x_ {i}}$${\ displaystyle f (x)}$

Deterministisk beslutningstreet

Hvis resultatet av et beslutningstreet er , for alle , sies beslutningstreet å "beregne" . Dybden på et tre er det maksimale antall spørsmål som kan skje før et blad er nådd og et resultat oppnådd. , Den deterministiske beslutningstreet kompleksitet er den minste dybde blant alle deterministiske beslutningstre som beregne . ${\ displaystyle f (x)}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$${\ displaystyle f}$${\ displaystyle D (f)}$${\ displaystyle f}$${\ displaystyle f}$

Tilfeldig beslutningstreet

En måte å definere et randomisert beslutningstre er å legge til flere noder i treet, hver kontrollert av en sannsynlighet . En annen ekvivalent definisjon er å definere den som en fordeling over deterministiske beslutningstrær. Basert på denne andre definisjonen er kompleksiteten til det randomiserte treet definert som den største dybden blant alle trærne til støtte for den underliggende fordelingen. er definert som kompleksiteten til det randomiserte beslutningstreet med det laveste dybde hvis resultat er sannsynlig i det minste for alle (dvs. med avgrenset tosidig feil). ${\ displaystyle p_ {i}}$${\ displaystyle R_ {2} (f)}$${\ displaystyle f (x)}$${\ displaystyle 2/3}$${\ displaystyle x \ in \ {0,1 \} ^ {n}}$

${\ displaystyle R_ {2} (f)}$er kjent som Monte Carlo randomiserte beslutningstreet kompleksitet, fordi resultatet får være feil med avgrenset tosidig feil. The Las Vegas beslutnings treet kompleksitet måler forventet dybden av et beslutningstre som må være korrekt (dvs. har null-feil). Det er også en ensidig begrenset feilversjon som er betegnet med . ${\ displaystyle R_ {0} (f)}$${\ displaystyle R_ {1} (f)}$

Ikke-deterministisk beslutningstreet

Den ikke-deterministiske beslutningstrekompleksiteten til en funksjon er oftere kjent som sertifikatkompleksiteten til den funksjonen. Den måler antall inngangsbiter som en ikke- deterministisk algoritme må se på for å evaluere funksjonen med sikkerhet.

Formelt er sertifikatets kompleksitet på at størrelsen på den minste delmengden av indekser slik at for alle , hvis for alle , da . Sertifikatkompleksiteten er den maksimale sertifikatkompleksiteten . Den analoge oppfatningen der man bare krever at verifisereren er korrekt med 2/3 sannsynlighet, er betegnet . ${\ 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)}$

Kvantebeslutningstreet

Kvantebeslutningstrekompleksiteten er dybden av det laveste dybde kvantebeslutningstreet som gir resultatet med sannsynlighet i det minste for alle . En annen størrelse,, er definert som dybden av det laveste dybde kvantebeslutningstreet som gir resultatet med sannsynlighet 1 i alle tilfeller (dvs. beregner nøyaktig). og er mer kjent som quantum query complexities , fordi den direkte definisjonen av et quantum beslutningstreet er mer komplisert enn i det klassiske tilfellet. I likhet med det tilfeldige tilfellet, definerer vi og . ${\ 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)}$

Disse forestillingene er vanligvis avgrenset av begrepene grad og omtrentlig grad. Den grad av , betegnet , er den minste grad av ethvert polynom tilfredsstillende for alle . Den omtrentlige graden av , betegnet , er den minste graden av noe polynom som tilfredsstiller når og når . ${\ 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) \ in [0,1 / 3]}$${\ displaystyle f (x) = 0}$${\ displaystyle p (x) \ in [2 / 3,1]}$${\ displaystyle f (x) = 1}$

Beals et al. etablert det og . ${\ displaystyle Q_ {0} (f) \ geq \ deg (f) / 2}$${\ displaystyle Q_ {2} (f) \ geq {\ widetilde {\ deg}} (f) / 2}$

Forholdet mellom målinger av kompleksitet i boolsk funksjon

Det følger umiddelbart fra definisjonene som for alle -biters boolske funksjoner , og . Å finne de beste øvre grensene i motsatt retning er et viktig mål innen spørringskompleksitet. ${\ 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}$

Alle disse typer spørringskompleksitet er polynomielt relatert. Blum og Impagliazzo, Hartmanis og Hemachandra og Tardos oppdaget uavhengig av det . Noam Nisan fant at Monte Carlo randomisert beslutningstre kompleksitet er også polynomially relatert til determinis beslutningstre kompleksitet: . (Nisan viste også at .) En strammere forhold er kjent mellom Monte Carlo og Las Vegas modeller: . Dette forholdet er optimalt opp til polylogaritmiske faktorer. Når det gjelder kvantebeslutningstrekompleksiteter,, og denne grensen er stram. Midrijanis viste at forbedring av en kvartikgrense på grunn av Beals et al. ${\ 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})}$

Det er viktig å merke seg at disse polynomiske forholdene bare gjelder for totale boolske funksjoner. For delvise boolske funksjoner , som har et domene en delmengde av , er en eksponentiell skille mellom og mulig; det første eksemplet på et slikt problem ble oppdaget av Deutsch og Jozsa . ${\ displaystyle \ {0,1 \} ^ {n}}$${\ displaystyle Q_ {0} (f)}$${\ displaystyle D (f)}$

Følsomhet antagelser

For en Boolske funksjon , er følsomheten av å defineres være den maksimale følsomhet av over alt , hvor følsomheten av ved er antall énbitsfeil endringer i at forandring av verdien av . Følsomhet er relatert til forestillingen om total innflytelse fra analysen av boolske funksjoner , som er lik gjennomsnittlig følsomhet over alt . ${\ 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}$

Den følsomhet formodning er den formodning at følsomheten polynomially relatert til spørring kompleksitet; det vil si at det eksisterer eksponent slik at for alle , og . Man kan vise gjennom et enkelt argument at , så antagelsen er spesielt opptatt av å finne en nedre grense for følsomhet. Siden alle de tidligere diskuterte kompleksitetsmålene er polynomielt relaterte, er den presise typen kompleksitetsmål ikke relevant. Imidlertid formuleres dette vanligvis som spørsmålet om å relatere følsomhet med blokkfølsomhet. ${\ 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)}$

Den blokk følsomhet av , betegnet , er definert til å være den maksimale blokken følsomheten over alt . Blokkfølsomheten til at er det maksimale antallet usammenhengende delmengder slik at, for et hvilket som helst av delmengdene , vender bitene som tilsvarer verdien av . ${\ 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)}$

Ettersom blokken følsomhet tar et maksimum i løpet av flere valg av undergrupper, . Videre er blokkfølsomhet polynomielt relatert til de tidligere diskuterte kompleksitetsmålene; for eksempel viste Nisans papir som introduserte blokkfølsomhet det . Så kan man omformulere følsomheten formodning som viser at for noen , . I 1992 antok Nisan og Szegedy at det var tilstrekkelig. Dette ville være stramt, da Rubinstein i 1995 viste en kvadratisk atskillelse mellom følsomhet og blokkfølsomhet. ${\ 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}$

I juli 2019, 27 år etter at formodningen opprinnelig ble presentert, beviste Hao Huang fra Emory University sensitivitetsgissingen, og viste det . Dette beviset er spesielt kortfattet, og beviser denne påstanden på to sider når tidligere fremgang mot følsomhetsgissingen hadde vært begrenset. ${\ displaystyle bs (f) = O (s (f) ^ {4})}$

Sammendrag av kjente resultater

Mest kjente separasjoner for kompleksitetstiltak per oktober 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

Denne tabellen oppsummerer resultater på skillet mellom målinger av kompleksiteten i Boolsk funksjon. Kompleksitetsmålene er, i rekkefølge, deterministiske, null-feil randomisert, tosidig-feil randomisert, sertifikat, randomisert sertifikat, blokkfølsomhet, følsomhet, nøyaktig kvantum, grad, kvante og tilnærmet gradskompleksitet.

Tallet i kolonnen -th og -th kolonne angir grenser på eksponenten , som er det minste av alle tilfredsstillende for alle boolske funksjoner . For eksempel er oppføringen i D-rad og sjette kolonne "3, 6", så for alle , og det finnes en funksjon slik at . ${\ 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)})}$

Se også

• Sammenligning sortering
• Beslutningstre
• Formodning om Aanderaa – Karp – Rosenberg
• Minimum spennende tre # Beslutningstrær

Referanser

Undersøkelser

• 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