Amit matematika történeti szempontból a 17. századnak az analízis, differenciál és integrálszámítás kialakulása jelentett, ugyanazt jelenti a 20. századnak a számítástechnika és számítástudomány. Az effektív kiszámíthatóság, algoritmusok általános elmélete a matematika formális megalapozására tett kísérletek egyik fontos mellékeredménye volt. A 30-as évek közepére Kurt Gödel, Alan Turing, Alonso Church, A.A. Markov, E. Post és sok más matematikus kutatásainak eredményeképpen az "elvben kiszámítható" intuitív fogalmára általánosan elfogadott matematikai definíciót sikerült adni. Ennek segítségével látványos eredmények milliárdjai születtek. Ezek egy-egy probléma, problémasereg algoritmikus megoldhatatlanságát bizonyítják. A sorban az elsőés talán legfontosabb Gödel eredménye, amiben Hilbert eldöntésproblémájának megoldhatatlanságát bizonyítja: ha adott egy kellő kifejezőerővel rendelkező, kezelhető formális rendszer (mint például a Peano aritmetika formulahalmaza a megfelelő levezetési szabályokkal, vagy a halmazelmélet valamely axiómarendszere, vagy akár valamilyen intuicionista levezetési rendszer), ahhoz nem található olyan algoritmus, ami minden állításról megmondaná, hogy a rendszer szabályainak megfelelően levezethető-e vagy sem. Ez a helyzet a csoportok és gyűrűk elméletével is: nem létezik algoritmus, amely mondjuk minden csoportelméleti állításról megmondaná, hogy teljesül-e vagy sem az összes csoportban. Ugyancsak algoritmikusan megoldhatatlan a parkettázási feladat: van véges sok fajta négyzet alakú csempénk, mindegyikből végtelen sok. El kell döntenünk, hogy lefedhető-e a teljes sík úgy, hogy a szomszédos csempék mintája illeszkedjen. Tetszőleges eljáráshoz tudunk konstruálni csempéket, hogy azokra az eljárás hibás eredményt fog adni.
A 30-as évek algoritmus-elmélete megmutatta: a bölcsek kövét hiábavalóság keresni. Ennek fontos filozófiai és ismeretelméleti hatásai vannak, nem véletlen hogy a filozófusok által legtöbbet idézett matematikai eredmény Gödel nem-teljességi tétele. Az 50-es évekre kristályosodtak ki az algoritmus elmélet fogalmai és a módszerei, általánosan elfogadottá váltak a nem kiszámítható, eldönthetetlen problémákról szóló tételek. Az elmélet azonban nem tudott intuitíve helyes képet adni az érme másik oldaláról, az elvben eldönthető állításokról. Ha egy probléma megoldására csak véges sok lehetőség van, elvben semmi problémát nem okoz megmondani hogy ezek közül valamelyik megfelelő-e vagy sem. Hogy ez gyakorlatban ténylegesen megtehető-e, például nem kell-e a döntéshez több esetet végignéznünk mint ahány részecskéből az egész univerzum áll, erről az algoritmusok általános elmélete nem tud számot adni.
A hatékony algoritmus fogalma csak a 60-as években került előtérbe elsősorban egy szovjet kibernetikus munkája nyomán. A cél az volt, hogy elvi különbséget tudjunk tenni az "összes eset végignézése" és az ennél gyorsabb, ravaszabb algoritmusok között. A választóvonalat a tapasztalat és elméleti megfontolások alapján a polinomiális időkorlát húzza meg. Az ilyen algoritmusok igen robosztus részosztályt alkotnak. Gondoljunk arra, hogy egy algoritmus futási ideje jelentősen függ például attól, milyen számítógépünk van, milyen számítástechnikai modell valósít meg, mennyire absztraktak az utasítások stb. A polinomiális idejű algoritmusok ezekre, a megoldandó feladat kódolására, és sok más, a feladat és algoritmus szemponjából másodlagos szempontokra érzéketlenek, így önmagukban is érdekes, vizsgálatra méltó osztályt alkotnának.
Természetesen az, hogy egy algoritmus polinomiális idejű nem jelenti azt, hogy a gyakorlatban is hatékonynak kellene tekintenünk, vagy hogy az ellenkezője automatikusan kizárja a használható eljárások közül. Például a lineáris programozási feladatok megoldására ma is legszélesebb körben alkalmazott eljárás ( a szimplex módszer ( nem polinomiális idejű. A polinomiális algoritmusok vizsgálata azonban ebből a szempontból is sikeres: ilyen algoritmus keresése gyakran a gyakorlatban is fontos és használható eredményre vezetett ( ahogyan ez a lineáris programozás esetében is történt. A talált polinomiális algoritmus segítségével egy sor olyan feladatot is sikerült gyors algoritmussal megoldani, melyekre korábban ilyen nem volt ismert.
Mást jelent az, hogy az eredmény helyességét ellenőrizni tudjuk, és mást az, hogy magát az eredményt ki is tudjuk számítani. Ez a kettősség az algoritmusok általános elméleténél is megvan. Ha adott egy bizonyítás, arról (algoritmikusan) könnyű eldönteni, hogy jó-e, míg ha csak a tétel adott, annak bizonyítását algoritmikusan lehetetlen megkeresni. Azokat a feladatokat, melyeket polinomiális idő alatt meg tudunk oldani, P-vel, azokat, melyeknél a megoldás helyességét tudjuk polinomiális idő alatt ellenőrizni, NP-vel jelöljük. (Itt P a polinomiális szó kezdőbetűje, N pedig a nem-determinisztikusé.) NP-beli feladat például n lányt és n fiút összeházasítani úgy, hogy csak ismerősök házasodhatnak. Ha valaki a párosítást megcsinálja, akkor gyorsan tudjuk ellenőrizni hogy az tényleg helyes-e. NP-beli az utazó ügynök problémája is: n városból bizonyosak között van repülőjárat. Van-e olyan repülős körút, amely minden várost pontosan egyszer érint? Vagy adott néhány fajta csempénk, ki tudunk tölteni velük szabályosan egy n-szer n-es négyzetet? További példa: adott egy összetett szám, írjuk fel két egynél nagyobb egész szám szorzataként.
Minden P-beli feladat egyúttal NP-ben is van. De van-e NP-ben olyan feladat, ami nem P-beli? Erre a kérdésre ma még nem tudjuk a választ. Nem tudjuk, vajon minden összetett számnak gyorsan meg tudjuk-e határozni egy prímtényezőjét, vagy hogy adott csempékre el tudjuk-e dönteni, kirakható-e belőlük egy négyzet. Amit tudunk, az Cook, Levin és Karp 1971-ből származó eredménye, ami szerint NP-ben léteznek a legnehezebb problémák. Ha ezek bármelyikére létezne polinomiális algoritmus, akkor minden NP-beli problémára is létezne. Több ezer ilyen NP-teljesnek nevezett problémát ismerünk, például a csempézés, az utazó ügynök problémája is ilyen, vagy például az is, hogy egy logikai kifejezés felvehet-e igaz (vagy hamis) értéket. Azt, hogy a P és NP osztályok különbözők, így jelöljük: P ( NP. Iparágak fejlődtek ki ezen a feltevésen, tíz év múlva akár gazdasági katasztrófát is okozhat, ha erről a sejtésről kiderülne, hogy hamis.
Vegyünk egy NP-beli problémát, mondjuk azt hogy adott csempékkel egy nagy négyzet kirakható-e helyesen. Ilyen megoldható feladatot könnyen elő tudok állítani a következő módon. Kirakom a négyzetet fehér csempékkel és utólag berajzolok egy mintát. Ezután fölszedem a csempéket és összekeverem őket. A csempéket újra kirakni nagyon nehéz, de persze én meg tudom csinálni, viszont rajtam kívül más senki (hacsak a minta nem volt vagy nagyon egyszerű vagy nagyon bonylult). Ez a tudás azonosít engem, igazolványként szolgál. Nyilvánosságra hozom a csempék halmazát. Ha valaki nem ismer és meg akar győződni arról, hogy tényleg én vagyok-e én, felszólít arra, hogy rakjam össze a csempéket. Gyorsan ellenőrizheti, hogy az összerakás tényleg rendben van-e. Minthogy rajtam kívül senki sem képes erre a mutatványra, sikerrel igazoltam magamat. Igazolvány, útlevél, hitelkártya, stb. készítése nagyon fontos, ezt mindenkor a készítők és a hamisítók küzdelme jellemezte. A bonyolultságelméleti kutatások új lökést adtak a titkosírástannak, magyarul kriptográfiának. Olyan okos kártyácskákat, igazolványokat fejlesztettek ki, melyek sikeres hamisítása ( ha nem is mondana ellent jelenlegi ismereteinknek ( azonnal átütő matematikai eredményt jelentene egy senki által nem várt irányban, miszerint P(NP mégsem igaz. Az okos kártyák (smart card), elektronikus vásárlás, elektronikus banki műveletek technológiája mögött a bizonyítatlan P(NP sejtés, vagy annak még erősebb formája áll.
A bonyolultságelmélet és a titkosírás közti mezsgyén megjelentek a véletlen algoritmusok. Egy igazolványnak biztonságosnak kell lennie nem csak a biztosra menő hamisítóval szemben, hanem azzal szemben is, aki rizikózik. Vállalja, hogy elkapják, ha a sikeres hamisítás nagy valószínűségű. Szóval tud-e segíteni, ha egy algoritmusban véletlen mennyiségeket is használhatunk? Az hogy igen, még a P ( NP sejtésnél is erősebb állítás, s így persze nem tudjuk igaz-e. Annak eldöntésére, hogy egy szám prím vagy összetett, gyors véletlen algoritmusokat ismerünk (de olyan nem, ami egy összetett szám prímtényezőit is szolgáltatná nagy valószínűséggel); ilyen determinisztikus algoritmust jelenleg csak a kiterjesztett Riemann-hipotézis fennállása esetén tudnak garantálni. Még érdekesebb, hogy determinisztikus algoritmusok készítésénél használhatunk véletlent. Az Ajtai, Komlós, Szemerédi által készített rendező hálózat eredetileg egy véletlen gráfból állt elő, s az elkészült hálózat nagy valószínűséggel minden számhalmazt jól rendezett meg. Szabad-e ilyen rendezőt mondjuk egy űrhajóba beépíteni, ha az kevesebb mint 10-10 valószínűséggel hibázik ( tudva, hogy mintegy 1 százalékra becsülik az űrhajó meghibásodását?
Ezzel elérkeztünk az előadás címében szereplő fogalomig: a majdnem jó bizonyításhoz. Hogyan lehetne egy bizonyítás csak 99 százalékig jó? Egy matematikai bizonyítás vagy teljesen jó, vagy ha csak egy picit is rossz, akkor tökéletesen rossz. Nincsenek majdnem jó bizonyítások, s ez különbözteti meg a matematikát a humán tudományoktól. Szóval mit tudunk tenni a "majdnem jó" bizonyításokkal? Mitől is lesz egy bizonyítás majdnem jó? Becslések szerint a matematikai folyóiratokban megjelent bizonyításoknak mintegy 35 százaléka hibás, míg a kimondott tételek közül kevesebb mint 5 százalék bizonyul hamisnak. A rossz bizonyítások jó része is "javítható", igazán kevés olyan bizonyítás van, ami reménytelenül rossz.
1991-92 során egy izgalmas tétel-vadászat melléktermékeként jött létre az átlátszó bizonyítás fogalma, többek között Lovász László egy eredménye után Babai László és Szegedy Márió munkája nyomán. Az eredmény minden folyóirat szerkesztő és lektor álma: a bizonyítások végigbogarászása helyett elegendő kevés véletlenszerűen választott helyen megnézni a cikket, és a kifigyelt helyeken talált értékekre egy egyszerű ellenőrzést elvégezni. Ha ez az ellenőrzés nem talál hibát, akkor ugyan azt nem tudja a lektor garantálni, hogy a bizonyítás jó, de azt igen, hogy nagy valószínűséggel a leírt bizonyításhoz közel található egy tökéletes bizonyítás is. Az átlátszó bizonyítás elkészítéséhez a szerzőnek persze dolgoznia kell, de a többletmunka nem jelentős. A matematikai eredmény nem matematikusoknak is felkeltette az érdeklődését, cikk jelent meg erről például a New York Times-ban is. Az algoritmus jelenlegi formájában még nem alkalmazható a szó szoros értelmében vett mindennapi életben fellelhető feladatokra. Ha a további kutatások a szükséges kódolások, átírások mennyiségét lényegesen csökkenteni tudják, akkor például a Hivatal előírhatja, hogy a kérvényező (értsd: adóbevalló) dokumentumait ilyen módon terjessze be. Ebben az esetben a Hivatal nem csak szúrópróba szerűen tud ellenőrizni, hanem minden egyes kérvény helyességét külön-külön is megvizsgálhatja. Kiragad kevés, véletlenszerűen választott ellenőrző pontot, az oda beírt értékeknek egy gyorsan kiszámítható összefüggést kell teljesíteniük. Minthogy a kérvényező nem tudja, mik lesznek az ellenőrző pontok, hibásan kitöltött kérvény ezen a gyors ellenőrzésen csak igen kicsi, mondjuk 10-10 valószínűséggel csúszhat át. Ez azt jelenti, ha mondjuk a Hivatal évi 10 millió kérvényt bírál el, akkor várhatóan ezer évenként egy hibás kérvényt fogad el helyesnek.
Az átlátszó bizonyítással kapcsolatos eredmények azzal kecsegtettek, hogy közelebb kerülünk az igazi nagy kérdés megoldásához, vagyis annak bizonyításához, hogy P(NP. Az eltelt idő azonban eddig nem igazolta ezeket a reményeket, s századunk nagy matematikai problémájának megoldása még mindig ugyanolyan távolinak látszik, mint 1971-es megfogalmazásakor.