Inkompressibilitetsmetod

Inom matematiken är inkompressibilitetsmetoden en bevismetod som den probabilistiska metoden , räknemetoden eller duvhålsprincipen . För att bevisa att ett objekt i en viss klass (i genomsnitt) uppfyller en viss egenskap, välj ett objekt i den klassen som är inkompressibelt . Om den inte uppfyller egenskapen kan den komprimeras med beräkningsbar kodning. Eftersom det generellt kan bevisas att nästan alla objekt i en given klass är inkompressibla, visar argumentet att nästan alla objekt i klassen har den inblandade egenskapen (inte bara genomsnittet). Att välja ett inkomprimerbart objekt är ineffektivt och kan inte göras av ett datorprogram. Ett enkelt räkneargument visar dock vanligtvis att nästan alla objekt i en given klass kan komprimeras med bara några få bitar (är inkompressibla).

Historia

Inkompressibilitetsmetoden beror på en objektiv, fixerad föreställning om inkompressibilitet. En sådan föreställning gavs av Kolmogorovs komplexitetsteorin , uppkallad efter Andrey Kolmogorov .

En av de första användningarna av inkompressibilitetsmetoden med Kolmogorovs komplexitet i beräkningsteorin var att bevisa att körtiden för en enbands Turing-maskin är kvadratisk för att acceptera ett palindromiskt språk och sorteringsalgoritmer kräver minst $n\log n$ tid att sortera $n$ objekt. En av de tidiga inflytelserika tidningarna som använde inkompressibilitetsmetoden publicerades 1980. Metoden tillämpades på ett antal områden, och dess namn myntades i en lärobok.

Ansökningar

Talteori

Enligt ett elegant euklidiskt bevis finns det ett oändligt antal primtal . Bernhard Riemann visade att antalet primtal mindre än ett givet tal är kopplat till nollorna i Riemanns zetafunktion . Jacques Hadamard och Charles Jean de la Vallée-Poussin bevisade 1896 att detta antal primtal är asymptotiskt till $n/\ln n$ ; se primtalssatsen (använd $\ln$ för den naturliga logaritmen och $\log$ för den binära logaritmen). Med hjälp av inkompressibilitetsmetoden GJ Chaitin på följande sätt: Varje $n$ kan beskrivas med sin primtalsfaktorisering $n=p_{1}^{n_{1 }}\cdots p_{k}^{n_{k}}$ (vilket är unikt), där $p_{1},\ldots ,p_{k}$ är de första $k$ primtal som är (högst) $n$ och exponenterna (eventuellt) 0. Varje exponent är (högst) $\log n$ , och kan beskrivas med $\log \log n$ bitar. Beskrivningen av $n$ kan ges i $k\log \log n$ bitar, förutsatt att vi vet värdet på $\log \log n$ (gör det möjligt för en att tolka de på varandra följande blocken av exponenter). För att beskriva $\log \log n$ kräver endast $\log \log \log n$ bitar. Med inkompressibiliteten för de flesta positiva heltal finns det för varje ${\displaystyle k>0} ett positivt heltal$$n$ med binär längd $l\approx \log n$ som inte kan beskrivas i färre än $l$ bitar. Detta visar att antalet primtal, $\pi (n)$ mindre än $n$ , uppfyller

$\pi (n)\geq {\frac {\log n}{\log \log n}}-o(1).$

Ett mer sofistikerat tillvägagångssätt som tillskrivs Piotr Berman (nuvarande bevis delvis av John Tromp ) beskriver varje inkompressibel $n$ av $k$ och $n/p_{k}$ , där $p_{k}$ är det största primtalet som delar $n$ . Eftersom $n$ är inkompressibel måste längden på denna beskrivning överstiga $\log n$ . För att tolka det första blocket i beskrivningen $k$ ges i prefixform $P(k)=\ log k+\log \log k+\log \varepsilon (k)$ , där $\varepsilon (k)$ är en godtycklig, liten, positiv funktion. Därför $\log p_{k}\leq P(k)$ . Därför, $p_{k}\leq n_{k}$ med $n_{k}=\varepsilon (k)k\log k$ för en speciell sekvens av värden $n_{1},n_{2},\ldots$ . Detta visar att uttrycket nedan gäller för denna speciella sekvens, och ett enkelt tillägg visar att det gäller för varje $n>0$ :

$\pi (n)\geq {\frac {n}{\varepsilon (n)\log n}}.$

Båda bevisen presenteras mer i detalj.

Grafteori

En märkt graf $G=(V,E)$ med $n$ noder kan representeras av en sträng $E(G)$ av ${n \choose 2}$ bitar, där varje bit indikerar närvaron (eller frånvaron) av en kant mellan nodparet i den positionen. $K(G)\geq {n \choose 2}$ och graden $d$ för varje vertex uppfyller

$|dn/2|=O\left({\sqrt {n\log n}}\right).$

För att bevisa detta med inkompressibilitetsmetoden, om avvikelsen är större kan vi komprimera beskrivningen av $G$ under $K(G)$ ; detta ger den motsägelse som krävs. Denna sats krävs i ett mer komplicerat bevis, där inkompressibilitetsargumentet används ett antal gånger för att visa att antalet omärkta grafer är

$\sim {\frac {2^{n \choose 2}}{n!}}.$

Kombinatorik

En transitiv turnering är en komplett riktad graf , $G=(V,E)$ ; if ${\displaystyle (i,j),(j,k)\in E} ,$ ( $\displaystyle (i,k)\in E}$ . Betrakta uppsättningen av alla transitiva turneringar på $n$ noder. Eftersom en turnering är en märkt, riktad komplett graf , kan den kodas av en sträng $E(G)$ av ${n \choose 2}$ bitar där varje bit indikerar riktningen på kanten mellan nodparet i den positionen. Med denna kodning innehåller varje transitiv turnering en transitiv subturnering på (minst) $v(n)$ hörn med

$v(n)\leq 1+\lfloor 2\log n\rfloor .$

Detta visades som det första problemet. Det är lätt att lösa med inkompressibilitetsmetoden, liksom myntvägningsproblemet, antalet täckande familjer och förväntade fastigheter; till exempel, minst en bråkdel av $1-1/n$ av alla transitiva turneringar på $n$ hörn har transitiva subturneringar på högst $1+2\lceil 2\log n\rceil$ hörn. $n$ är tillräckligt stor.

Om ett antal händelser är oberoende (i sannolikhetsteorin ) av varandra, kan sannolikheten att ingen av händelserna inträffar enkelt beräknas. Om händelserna är beroende blir problemet svårt. Lovász lokala lemma är en princip att om händelser är mestadels oberoende av varandra och har en individuellt-liten sannolikhet, finns det en positiv sannolikhet att ingen av dem kommer att inträffa. Det bevisades med inkompressibilitetsmetoden. Med hjälp av inkompressibilitetsmetoden visades det existera flera versioner av expander- och superkoncentratorgrafer.

Topologisk kombinatorik

I Heilbronn-triangelproblemet kastar du $n$ punkter i enhetskvadraten och bestämmer maximalt av den minimala arean av en triangel som bildas av tre av punkterna över alla möjliga arrangemang. Detta problem löstes för små arrangemang, och mycket arbete gjordes på asymptotiska uttryck som en funktion av $n$ . Den ursprungliga gissningen om Heilbronn var $O(1/n^{2})$ under tidigt 1950-tal. Paul Erdős bevisade att denna gräns är korrekt för ${\displaystyle n} ,$ ett primtal. Det allmänna problemet förblir olöst, bortsett från den mest kända nedre gränsen ${\displaystyle \Omega ((\log n)/n^{2})} ($ uppnåelig; därför Heilbronn s gissning är inte korrekt för allmän $n$ ) och övre gräns $\exp(c{\sqrt {\log n}})/n ^{8/7}$ (bevisat av Komlos, Pintsz och Szemeredi 1982 respektive 1981). Med hjälp av inkompressibilitetsmetoden studerades medelfallet. Det bevisades att om området är för litet (eller stort) kan det komprimeras under Kolmogorov-komplexiteten för ett enhetligt-slumpmässigt arrangemang (hög Kolmogorov-komplexitet). Detta bevisar att för den överväldigande majoriteten av arrangemangen (och förväntningarna) är arean av den minsta triangeln som bildas av tre av $n$ punkter som kastas likformigt slumpmässigt i enhetskvadraten ${ \displaystyle \Theta (1/n^{3})}$ . I det här fallet bevisar inkompressibilitetsmetoden de nedre och övre gränserna för den inblandade egenskapen.

Sannolikhet

Lagen för den itererade logaritmen , lagen för stora tal och upprepningsegenskapen visades hålla med hjälp av inkompressibilitetsmetoden och Kolmogorovs noll–ett lag , med normala tal uttryckta som binära strängar (i betydelsen E. Borel ) och fördelningen av 0:or och 1:or i binära strängar med hög Kolmogorov-komplexitet.

Turingmaskinens tidskomplexitet

Den grundläggande Turing-maskinen, som utformades av Alan Turing 1936, består av ett minne: ett band med potentiellt oändliga celler på vilka en symbol kan skrivas och en finit kontroll, med ett läs-skrivhuvud fäst, som skannar en cell på bandet. Vid varje steg kan läs-skrivhuvudet ändra symbolen i cellen som skannas och flytta en cell åt vänster, höger eller inte alls enligt instruktioner från den finita kontrollen. Turingmaskiner med två bandsymboler kan övervägas för bekvämlighets skull, men detta är inte nödvändigt.

1968 visade FC Hennie att en sådan Turing-maskin kräver order ${\displaystyle n^{2}} för att i$ värsta fall kunna känna igen språket för binära palindromer . 1977 presenterade WJ Paul ett inkompressibilitetsbevis som visade att ordning $n^{2}$ tid krävs i genomsnittsfallet. För varje heltal $n$ , överväg alla ord av den längden. För enkelhetens skull bör du överväga ord med den mellersta tredjedelen av ordet bestående av nollor. Den accepterande Turing-maskinen slutar med ett acceptläge till vänster (början av bandet). En Turing-maskinberäkning av ett givet ord ger för varje plats (gränsen mellan intilliggande celler) en sekvens av korsningar från vänster till höger och höger till vänster, varje korsning i ett speciellt tillstånd av den ändliga kontrollen. Positioner i den mellersta tredjedelen av ett kandidatord har alla en $) {\displaystyle O(n^{2} )}$ sekvens av längden $O(n)$ (med en total beräkningstid på ), eller så har någon position en korsningssekvens av $o(n)$ . I det senare fallet kan ordet (om det är ett palindrom ) identifieras av den korsningssekvensen.

Om andra palindromer (som slutar i ett accepterande tillstånd till vänster) har samma korsningssekvens, är ordet (bestående av ett prefix upp till positionen för den inblandade korsningssekvensen) för den ursprungliga palindromen sammanlänkad med ett suffix den återstående längden av den andra palindrom skulle också accepteras. Om man tar palindromen för $\Omega (n)$ , är Kolmogorov-komplexiteten som beskrivs av $o(n)$ bitar en motsägelse.

Eftersom den överväldigande majoriteten av binära palindromer har en hög Kolmogorov-komplexitet, ger detta en lägre gräns för den genomsnittliga körtiden i fallet . Resultatet är mycket svårare och visar att Turingmaskiner med $k+1$ arbetsband är mer kraftfulla än de med $k$ arbetsband i realtid (här en symbol per steg).

1984 visade W. Maass och M. Li och PMB Vitanyi att simuleringen av två arbetsband med ett arbetsband av en Turing-maskin tar $\Theta (n^{2})$ tid deterministiskt (optimalt, att lösa ett 30-årigt öppet problem ) och $\Omega (n^{2}/(\log n\log \log n) )$ tid icke-deterministiskt (i, detta är $\Omega (n^{2}/(\log ^{2}n\log \log n))$ Fler resultat angående band, stackar och köer , deterministiskt och icke-deterministiskt, bevisades med inkompressibilitetsmetoden.

Teori om beräkning

Heapsort är en sorteringsmetod, uppfunnen av JWJ Williams och förfinad av RW Floyd , som alltid körs i ${\displaystyle O(n\log n)}-$ tid. Det är tveksamt om Floyds metod är bättre än Williams i genomsnitt, även om den är bättre i värsta fall. Med hjälp av inkompressibilitetsmetoden visades det att Williams metod körs i genomsnitt på $2n\log n+O(n)$ tid och Floyds metod körs i genomsnitt i $n\log n+O(n)$ tid. Beviset föreslogs av Ian Munro .

Shellsort , upptäckt av Donald Shell 1959, är en jämförelsesort som delar upp en lista som ska sorteras i underlistor och sorterar dem separat. De sorterade underlistorna slås sedan samman och återskapar en delvis sorterad lista. Denna process upprepas ett antal gånger (antalet pass). Svårigheten med att analysera komplexiteten i sorteringsprocessen är att den beror på antalet $n$ nycklar som ska sorteras, på antalet $p$ av passeringar och ökningarna som styr spridningen i varje pass; underlistan är listan över nycklar som är inkrementparametern isär. Även om denna sorteringsmetod inspirerade ett stort antal tidningar, konstaterades bara det värsta fallet. För den genomsnittliga körtiden, endast det bästa fallet för en två-pass Shellsort och en övre gräns för $O(n^{23/15})$ för en viss inkrementsekvens för tre- pass Shellsort etablerades. En allmän nedre gräns för en genomsnittlig $p$ -pass Shellsort gavs vilket var det första framsteg i detta problem på fyra decennier. I varje pass flyttar jämförelsesorteringen en nyckel till en annan plats ett visst avstånd (en väglängd). Alla dessa väglängder är logaritmiskt kodade för längd i rätt ordning (av passeringar och nycklar). Detta tillåter rekonstruktion av den osorterade listan från den sorterade listan. Om den osorterade listan är inkompressibel (eller nästan så), eftersom den sorterade listan har nära noll Kolmogorov-komplexitet (och väglängderna tillsammans ger en viss kodlängd) måste summan vara minst lika stor som Kolmogorov-komplexiteten för den ursprungliga listan . Summan av väglängderna motsvarar körtiden, och körtiden är lägre i detta argument av $\Omega (pn^{1+1/p})$ . Detta förbättrades till en nedre gräns av

$\Omega \left(n\summa _{k=1}^{p}h_{k-1}/h_{k}\right )$

där $h_{0}=n$ . Detta innebär till exempel den nedre gränsen för Jiang-Li-Vitanyi för alla $p$ -pass inkrementsekvenser och förbättrar den nedre gränsen för särskilda inkrementsekvenser; den övre gränsen för Janson-Knuth matchas av en nedre gräns för den använda inkrementsekvensen, vilket visar att tre pass Shellsort för denna inkrementsekvens använder $\Theta (n^{23/15})$ inversioner.

Ett annat exempel är följande. $n,r,s$ är naturliga tal och ${\displaystyle 2\log n\leq r,s\leq n/4} ,$ det visades att för varje $n$ finns en boolesk $n\times n$ matris; varje $s\times (nr)$ delmatris har en rangordning på minst $n/2$ enligt inkompressibilitetsmetoden.

Logik

Enligt Gödels första ofullständighetsteorem finns det sanna (men obevisbara) påståenden eller satser i varje formellt system med beräkningsbart uppräknade satser (eller bevis) starka nog att innehålla Peano-arithmetik . Detta bevisas av inkompressibilitetsmetoden; varje formellt system $F$ kan beskrivas ändligt (till exempel i $f$ -bitar). I ett sådant formellt system kan vi uttrycka $K(x)\geq |x|$ eftersom den innehåller aritmetik. Givet $F$ och ett naturligt tal $n\gg f$ , kan vi söka uttömmande efter ett bevis på att någon sträng $y$ med längden $n$ uppfyller $K(y)\geq n$ . På detta sätt får vi den första sådana strängen; $K(y)\leq \log n+f$ : motsägelse.

Jämförelse med andra metoder

Även om den probabilistiska metoden generellt visar att det finns ett objekt med en viss egenskap i en klass, tenderar inkompressibilitetsmetoden att visa att den överväldigande majoriteten av objekten i klassen (genomsnittet eller förväntan) har den egenskapen. Det är ibland lätt att förvandla ett probabilistiskt bevis till ett inkompressibilitetsbevis eller vice versa. I vissa fall är det svårt eller omöjligt att förvandla ett bevis genom inkompressibilitet till ett probabilistiskt (eller räknande bevis). I praktiskt taget alla fall av Turing-maskinens tidskomplexitet som citeras ovan, löste inkompressibilitetsmetoden problem som hade varit öppna i årtionden; inga andra bevis är kända. Ibland kan ett bevis genom inkompressibilitet förvandlas till ett bevis genom att räkna, vilket hände i fallet med den allmänna nedre gränsen för körtiden för Shellsort .