Ohanterbara problem

Finns det problem som kräver så mycket beräkningar att inte ens datorer kan lösa dem? Ja. Och inte ens framtidens datorer kommer att kunna rå på så kallade intraktabla problem, trots att de kan vara lätta att formulera. Problem kan vara så komplicerade att mänskligheten inte har resurser att lösa dem. Med datorernas hjälp har lösningar till mycket komplicerade problem kunnat hittas.

Väderleksprognoser är ett exempel på enormt datorkrävande problem som skulle vara hopplösa utan datorer. Men det finns uppgifter som vi faktiskt inte kan få hjälp att lösa, vare sig nu eller i framtiden – inte för att de är principiellt olösliga, utan för att de är oerhört svåra att hantera.

Ett exempel på ett mycket lättformulerat men oerhört svårlöst problem kallas ”den resande handelsmannen” (se Det klarar datorerna aldrig av, F&F 4/97). Den handelsresande vill besöka ett givet antal städer en gång vardera, i den ordning som gör färdsträckan så kort som möjligt. Avstånden mellan alla städer är kända. Efter trippen vill handelsmannen återvända till utgångspunkten. I vilken ordning ska han besöka städerna för att minimera den totala färdsträckan? Det är inte svårt att exakt lösa problemet för fem städer, men fallet 100 städer är komplett ohanterligt!

Problemet är att informationsteoretikerna inte har funnit några metoder för att exakt lösa problemet som är bättre än att prova alla alternativ, dvs alla tänkbara färdsträckor. Det blir då ett exponentiellt antal beräkningssteg. Eftersom antalet beräkningssteg stiger mycket fort med antalet städer, kommer vi till slut till en punkt då resurserna, datorkapaciteten, inte räcker till. Mycket talar för att vi aldrig kommer att kunna lösa detta problem när ett stort antal färdsträckor måste beräknas.

För att få en känsla för svårigheterna kan vi tänka oss att handelsmannen vill besöka 100 orter. Antalet möjliga kombinationer av färdvägar blir då 100·99·98·…·1 > 10¹⁵⁸, vilket kan skrivas ut som en etta följd av 158 nollor.

De snabbaste parallelldatorerna kan i dag utföra ca 1 000 miljarder operationer per sekund. Beräkningen av färdsträckan för varje kombination kräver ca 100 operationer. Varje färdsträcksberäkning tar alltså 1/10 miljarddels sekund. Då skulle datorn varje år kunna testa 3,2 · 10¹⁷ kombinationer. Proceduren att gå igenom alla alternativen skulle alltså ta ca 10¹⁴⁰ år i anspråk! Den tiden kan jämföras med universums ålder, som är cirka 10¹⁰ år.

Problem av den här typen, där inte ens de snabbaste datorerna räcker till, kallas intraktabla. Den resande handelsmannens problem verkar höra hit.

**Ingen kan lösa**
Den österrikiske logikern Kurt Gödel bevisade år 1931 att vissa problem inom matematiken är olösbara. Men intraktabla problem är någonting annat. Lösningarna på problemen är här definierade av förutsättningarna och kan relativt enkelt förstås. Svårigheterna ligger i att själva lösningsförfarandet är så komplicerat att ingen människa, ingen dator och inte heller någon process i naturen kan ta oss fram till svaret. Det finns även andra områden med stora problem att finna lösningar. Inom kaosteorin kan osäkerheten om själva förutsättningarna, eller begynnelsevillkoren, begränsa möjligheterna att hitta rätt svar, även om lösningsförfarandet i sig kan vara enkelt. Kaosteorin har visat på en flora av intraktabla problem. En orsak till flera av dessa är den ”taggighet” som finns i naturen. Studerar vi strukturen av vissa grönsaker, av blad eller av ett lands kustlinje upptäcker vi återkommande s k fraktala mönster långt ner på mikroskopisk nivå. Vissa problem som har att göra med denna komplexa struktur är inte endast intraktabla, utan även olösliga; inte ens en god uppskattning kan beräknas med våra begränsade resurser för beräkningar.

Ett visst hopp för svårlösta problem har börjat gro under de senaste åren. Både teoretiskt och experimentellt har man visat att system av vissa sammansatta atomer eller molekyler, med hjälp av laserpulser, kan fås att bete sig som de logiska enheter som bygger upp vanliga datorer. Förutom småskaligheten har denna kvantdator en enorm fördel: den kan under beräkningens gång ligga i ett kvantmekaniskt tillstånd mellan den traditionella datorns 0- och 1-lägen. Ett mittemellanläge. En beräkning utifrån givna startvärden innehåller därför alla möjliga lösningar, tills systemet avkrävs ett svar. Det talas därför om att kvantdatorn kan simulera verkliga och komplexa förlopp (se *Efter kiselchipset*, F&F 1/02). Utvecklingen av kvantdatorn är intressant men problemfylld. Innan vi kan utnyttja dess potential krävs mycket forskning. Intraktabilitet är dessutom modellberoende. Även om en formulering av ett problem är intraktabel behöver en annan inte vara det. Ett enkelt exempel är operationen att subtrahera en ändlig men intraktabel integral från sig själv (se exempel i rutan interaktion). Exemplen illustrerar hur till synes enkla problemställningar kan visa sig vara intraktabla. Det finns ingen väg runt problemet: om vi vill vara helt säkra på att beräkningen utförs inom den noggrannhet som vi specificerat, står det utom mänsklig förmåga att utföra beräkningen. Även om datorutvecklingen går framåt kommer beräkningskapaciteten till slut att nå en gräns där den ändliga hastigheten (ljusets) och materialens finstruktur (halvledarelektroniken kan inte komprimeras bortom atomära dimensioner) blir avgörande. Även om problemen ovan kommer att kunna lösas inom överskådlig tid kan vi således formulera liknande problem som kräver ännu större noggrannhet – och som därmed är intraktabla för tid och evighet.

**Behöver inte vara komplexa**
Det finns alltså ett stort antal problem, ofta enkelt formulerade, som är intraktabla. Men hur ska vi ställa oss till lösningar som är alltför komplexa för att kunna hanteras av en människa? Intraktabla problem behöver inte alls vara särskilt komplexa. Den resande handelsmannens problem är ju tvärtom både enkelt att förstå och, visar det sig, relativt enkelt att lösa, om än oerhört tidsödande.

Ett exempel på komplexa problem är Goldbachs teorem, som säger att alla jämna heltal kan skrivas som summan av två primtal. Trots att teoremet är så lättformulerat och begripligt har ingen lyckats bevisa påståendet.

Ett annat problem, Fermats sista sats (se rutan nedan), stod under mer än 350 år emot en veritabel anstormning av påstådda bevis. Det generella beviset visade sig vara oerhört svårfångat, och dess lösning skulle innebära en av 1900-talets stora matematiska sensationer. Den 23 juni 1993 lade den brittiske matematikern Andrew Wiles, verksam vid Princeton University i USA, fram ett bevis för satsen, efter att ha arbetat ensam och isolerad med problemet i sju år. Manuskriptet omfattar ca 200 sidor och bygger till stora delar på moderna resultat inom talteorin – tolkningsbart för endast en bråkdel av yrkesmatematikerna. På grund av sakens tyngd användes så många som sex granskare av beviset i samband med publiceringen. Ett fel upptäcktes faktiskt, och Wiles fick den obehagliga uppgiften att under trycket från hela matematikervärlden fylla igen hålet som uppstått. Efter över ett år, när han var på vippen att ge upp, kunde han äntligen visa upp ett bevis som numera anses vara vattentätt. Alltsammans ger upphov till frågan om vad som egentligen krävs för att ett påstått bevis ska kunna accepteras som korrekt, och tas som allmän egendom.

Man kan fundera över ytterligare ett berömt exempel, fyrfärgsteoremet. Det säger att fyra färger räcker för att färglägga vilken karta som helst utan att angränsande länder får samma färg. Det formulerades i slutet av 1800-talet. År 1976 hävdade Kenneth Appel och Wolfgang Haken vid University of Illinois att teoremet är korrekt och att de har visat detta. Ändå kunde ingen utomstående kontrollera beviset! Deras första steg var att på sedvanligt analytiskt vis (med papper och penna) visa att varje tänkbar karta kan betraktas som sammansatt av vissa enklare grundkartor, tillsammans ca 2 000 stycken. Om teoremet kunde bevisas gälla för var och en av alla dessa grundkartor, skulle saken vara klar. Problemet var nu att en analytisk kontroll skulle ta oerhört lång tid. Därför valde de i stället att skriva ett datorprogram som, efter cirka 1 000 timmars arbete, utförde jobbet åt dem. Resultatet blev positivt: teoremet var sant. Men hur ska vi kunna hysa tilltro till ett bevis som ingen människa kan utföra på egen hand? Alla som har skrivit datorprogram vet hur lätt olika fel kan smyga sig in. Det kan handla om rena skrivfel, programmeringslogiska fel eller rentav en bristfällig eller felaktig algoritm. Och hur ska vi kunna gardera oss mot bedrägeri? Ett avsiktligt felaktigt ”datorbevis” kan göras så komplicerat att ingen förmår kontrollera det . . .

En utväg är att bara acceptera analytiska bevis, utförda utan datorhjälp. En sådan åtgärd skulle dock krympa mängden tillgängliga teorem i matematiken och därmed begränsa matematikens tillväxt och utveckling, vilket inte heller är önskvärt. En annan viktig aspekt är att enkelt formulerade, men ändå svårlösliga, problem alltid har haft en stark attraktionskraft på matematikerna. I stort sett varje matematiker, och många naturvetare, har ägnat några timmar åt att försöka härleda fyrfärgsteoremet. Somliga matematiker har ägnat hundratals fåfänga timmar åt problemet. Om nu problemet är analytiskt olösbart har datorbeviset en oerhörd betydelse genom att det leder uppmärksamheten bort från en stor och onödigt förspilld forskarmöda, mot nya fronter.

Onekligen är datorer till hjälp. År 1993 löstes delvis det synbarligen enkla men oväntat hårdkokta ”partyproblemet” av matematikerna Stanislaw P Radziszowski, Rochester Institute of Technology, USA, och Brendan D McKay, Australian National University, Canberra. Det berör relationer mellan en samling personer och lyder som följer: Vilket är det minsta antalet personer som garanterar att åtminstone x personer känner varandra gemensamt eller att minst y personer är ömsesidigt obekanta med varandra? Detta tal är känt som Ramsey-talet efter en brittisk matematiker. Radziszowski och McKay visade att Ramsey-talet för fallet fyra vänner och fem obekanta är 25. De löste problemet med hjälp av ett datorprogram, som om det hade utförts av en vanlig bordsdator hade tagit ett tiotal år att köra. Problemet handlar alltså om på vilka sätt olika personer på ett party kan vara relaterade till varandra. Det visar att vårt sunda förnuft kan leda oss fel när det gäller att uppskatta ett problems komplexitet, i detta fall antalet möjliga relationer. Poängen är att vi inte har någon aning om gästernas inbördes relationer när vi bjuder dem.

Lärdomen är, förutsatt att det faktiskt inte finns genvägar till beviset, att relativt banal kunskap, som just Ramsey-talet för ett givet fall, kan kosta oerhört mycket resurser. Datortid kan ju omräknas till pengar. Om vi kan uppskatta att exempelvis Ramsey-talet för fallet fem vänner och fem obekanta skulle ta 100 gånger mer datortid i anspråk, kanske vi väljer att inte härleda talet. Vi sätter då alltså en gräns för vår kunskap. Inte därför att vårt problem är olösbart, utan därför att det kräver för mycket resurser i förhållande till nyttan av problemets lösning. Vi närmar oss alltså nu åter dilemmat med intraktabla problem.

En mycket trolig utveckling inom ren och tillämpad matematik utkristalliseras. I takt med utvecklingen av kraftfulla datorer kan till slut vår mänskliga förmåga komma till korta, eftersom vi är alltför ineffektiva. Vi rådfrågar då datorn: Är detta påstående sant? Och får svaret: Ja, men beviset är alltför komplicerat för en människa…

**Svårt eller olösligt?**
Sammanfattningsvis kan man säga att formella problem måste tillhöra någon av följande kategorier.

1. Problemet är Gödel-olösbart (exempel på sådana problem är Cantors kontinuumhypotes; det finns ingen talmängd som är större än mängden av de naturliga talen, men mindre än mängden av de reella talen)
2. Lösning finns, men problemet är intraktabelt (exempel: handelsresandeproblemet)
3. Datorberäkningar kan ge lösningen, som är komplex och därför ohanterlig för människan (exempel: fyrfärgsteoremet)
4. Analytisk lösning existerar, men den är oöverblickbar för individen (exempel: klassificeringen av ändliga grupper, se nedan)
5. Problemet är analytiskt lösbart och verkligen överblickbart (exempel: Pythagoras sats).

Kategorierna 3 och 4 innehåller problem som har hög komplexitet. Beviset för den s k klassificeringen av ändliga grupper sammanfördes i början av 1980-talet, och utgör ca 500 artiklar om totalt 15 000 sidor, författade av mer än hundra forskare. En av forskarna, numera död, ansågs förstå beviset i dess vida omfattning.

För närvarande finns dessvärre ingen klar uppfattning om hur oceanen av oupptäckta teorem fördelar sig inom de fem kategorierna.Som en genväg till formulering av satser har experimentell matematik trätt fram. Komplexa samband tas då fram på ”empirisk” väg snarare än att härledas formellt. Resultaten blir ”sannolika bevis”, vilket är något helt annat än vad som krävs inom traditionell formell analys. Experimentell matematik ger inte visshet, men man ska inte förakta den insikt och intuition som blir följden av utövandet – och som i sin tur kan leda till nya upptäckter och teorem. Oavsett utvecklingen inom datorområdet måste vi inse att den enorma utvecklingen på beräkningskapacitetens område inte kommer att nå ifatt de frågor vi formulerar om intraktabla problem. De komplexa problemen, som människan i dag bara kan lösa med datorhjälp, är orsak nog att fundera över vad vi egentligen kommer att veta säkert i den framtida matematiken och naturvetenskapen. Många till synes enkla problem är helt enkelt ohanterliga. Vi har därmed anlänt till en punkt där vi tvingas vända vårt tänkande bort från förhoppningen om att sakta men säkert få svar på alla våra frågor, mot ett mer ödmjukt förhållningssätt där själva problemformuleringen och lösningsmetoden kommer i centrum.