Vekst av kombinasjonsmuligheter

Lysets hastighet er enorm. En lysstråle som forlater jorden i dag, vil om ett år ha nådd om lag 9,5 billioner kilometer ut i rommet. Men om to år vil den bare ha nådd dobbelt så langt, om ti år ti ganger så langt, og om n år n ganger så langt. Selv om hastigheten er stor, øker avstanden lyset tilbakelegger bare proporsjonalt, altså lineært, med antall år.

Når vi studerer kombinasjoner, øker imidlertid antall kombinasjonsmuligheter eksponentielt med antall elementer tilgjengelig. Hvis vi doblet antall kamper i ei tipperekke fra 12 til 24, ville ikke antall kombinasjonsmuligheter bli doblet, men øke fra 3¹² til 3²⁴, det vil si fra litt over fem hundre tusen til nesten tre hundre milliarder.

Eksempel 1:

I sjakk finnes det 20 forskjellige måter hvit kan åpne på (16 flytt med bønder og 4 med springere), og 20 måter svart kan svare på. Det gir totalt 400 kombinasjonsmuligheter allerede i første trekk. Nøyaktig hvor mange måter en kan flytte på i senere trekk vil avhenge av hvilke trekk som tidligere er gjort, men antall kombinasjoner øker uansett eksponentielt med antall trekk. Selv det kraftigste sjakkprogram klarer derfor ikke å vurdere kombinasjonene av alle mulige trekk i et parti fra åpning til slutt.

Eksempel 2:

Det sies at en ape med en skrivemaskin før eller siden vil skrive Shakespeares samlede verker. Tanken bak dette er at det finnes et endelig antall skrifttegn, og derved et endelig antall kombinasjoner av skrifttegn. Problemet er bare at antall kombinasjonsmuligheter vokser eksponentielt med antall tegn.

La oss for enkelhets skyld si at skrivemaskinen har 30 tegn tilgjengelig, de 26 latinske bokstavene a-z pluss 4 skilletegn. Så setter vi oss fore å skrive ned alle mulige tekster med et gitt antall tegn, og vi bruker 0,2 sekunder per tegn.

For en tekst med ett tegn vil det finnes 30 muligheter, som totalt tar 30 · 0,2 = 6 sekunder å skrive.

For en tekst med to tegn vil det finnes 30 · 30 = 900 muligheter, som totalt tar 900 · (0,2 + 0,2) = 360 sekunder å skrive, altså 6 minutter.

For en tekst med seks tegn vil det finnes 30⁶ = 729 000 000 muligheter, som totalt tar 729 000 000 · (6 · 0,2) = 874 800 000 sekunder å skrive. Dette er om lag 27,7 år.

For en tekst med tolv tegn vil det finnes 30¹² ≈ 5,3 · 10¹⁷ muligheter, som totalt tar 5,3 · 10¹⁷ · (12 · 0,2) ≈ 1,3 · 10¹⁸ sekunder å skrive. Dette er om lag 40 milliarder år, noe som er 8 ganger mer enn det som regnes som den gjenstående levetiden til solen.

Så vi skjønner at det vil ta sin tid før Shakespeares samlede verker blir ferdige med denne metoden.

Eksempel 3:

Grunnen til at det ofte kreves at passord skal inneholde små og store bokstaver, tall og spesialtegn, samt være av en viss lengde, er å gjøre antall mulige passord så mange at det blir vanskelig for en angriper å gjette seg fram til passordet. Antall mulige passord øker nemlig eksponentielt med både lengden og antall mulige tegn. La oss si at en datamaskin kan gjette en milliard kombinasjoner i sekundet. Regner vi med 29 bokstaver, 10 tall og 30 spesialtegn, viser tabellen under hvor lang tid datamaskinen vil bruke på å prøve alle mulige kombinasjoner, avrundet til hele enheter.

Vi ser at vi ved å øke lengden fra 8 til 12 tegn og å inkludere alle tegntyper, går fra ca. 8 minutter til nesten 25 millioner år.