ansans vitleysa

Afhverju skiptir máli að ansa? Er einhver munur á því að svara aldrei fyrsta póstinum og að hunsa eftir ansans póstinn? (s.s. svar svarsins).

Munurinn er meiri heldur en mann myndi gruna. Því í tölvupóstssamskiptum erum við að einhverju leyti að eiga formleg samskipti þar sem aðeins er notast við gögn (og þá yfirleitt bara bókstafi) en það eru til sannanir á því hversu stóran flækjuflokk (e. class of computational complexity) má ná utanum með mismunandi nálgunununum tveimur. Ef allt þarf að vera for-ritað þá er flækjuflokkurinn sem við náum utanum mun minni heldur en ef við megum tala saman. Svo mikið minni að það er nánast ótrúlega mikill munur!

Þegar engin samskipti eiga sér stað og sönnun þarf að vera sett fram á kjurru formi (e. statically) þá erum við í þeirri stöðu að sumar sannanir þyrftu að vera veldisvaxandi í stærð á framsetningu m.t.t. inntaks. Þetta er MJÖG merkileg niðurstaða því að einhverju leyti segir hún okkur frá mörkum stærðfræðinnar sem samskiptatækis.

Þetta er s.s. í samhengi við hversu mikið flækjustig við náum utanyfir þegar við megum tala saman en sá flokkur heitir IP (e. interactive polynomial time).

Sá flokkur sem fólk þekkir oft best er NP flokkurinn en sú fræga spurning hvort NP=P er einmitt um það hvort að við getum vitað eðlisfræði heimsins nógu vel til þess að ekki sé til frjáls vilji (enska spurningin spyr hvort til sé "nondeterminism"). Þessi spurning er því ekki beint alvarleg stærðfræði að mínu mati (eða a.m.k. meikar ekkert sens að reyna sanna að P sé eða sé ekki NP, bara vegna þess hvernig þessum skilgreiningum er stillt upp). Hinsvegar er miklu meira áhugavert að pæla í hversu stór PSPACE er því það er jú stærsti flokkurinn sem við (raunsæju) mennirnir getum náð í en hann er víst stærri en NP! En það kemur ekki á óvart þar sem PSPACE leyfir endalaust mikla reiknigetu í endanlega miklu rúmi (sem er þó hlutfallsbundið við inntak frekar en að vera skorðað við fasta af einhverju tagi).

Hugmyndin með NP er að ef einhver finnur sönnun þá sé hægt að fara yfir hana á viðráðanlegum tíma, þannig að það sem þetta "N" snýst um er að við vitum ekki hvernig á að leita af sönnunninni. Ef einhver gæfi okkur lykil að heiminum; sönnu eðlisfræðina (eða álíka háfleygt dæmi: "töfrahatt") þá væri hægt að fiska rétta svarið uppúr töfrahattinum og svo vera viss um að það sé rétt á viðráðanlegum tíma. Þannig má sjá stærðfræðisannanir (sem sumar hverjar voru ótrúlega litlar nálar í ótrúlega stórum heystakki - þangað til þær fundust) sem svör sem komu uppúr hattinum einhvernveginn, en þegar þau svör hafa komið upp úr hattinum þá er erfitt að véfengja niðurstöðuna (því það er viðráðanlegt að sannreyna niðurstöðuna). Þessi eiginleiki er því forsendan sem við byggjum stærðfræði sem samskiptatól á, við höfum ekkert að gera við sannanir sem eru svo ótrúlega stórar eða sem tekur svo ótrúlega langan tíma að fara yfir að ekki er í raun hægt að fara yfir þær.

Þessvegna er svo ótrúlega merkilegt að IP=PSPACE því það sem það þýðir er að allt sem getur verið reiknað út (sama hversu mikin tíma það tekur að reikna það) án þess að nota meira en margliðuvaxandi rými (m.t.t. inntaks) getur verið sannað ef við leyfum bara samskipti. Án samskipta (eins og kom fram fyrir þrem málsgreinum) þá yrði framsetningin á svarinu svo stór m.t.t. spurningunnar að það væri ekki gagnlegt. En með því að notast við samskipti þá er hægt að koma til skila jafnvel þessum sönnunum.

Þeir sem eru skilningsríkir nýtast því einstaklega vel í samskiptum því þannig er hægt að læra lausnir sem ekki er hægt að læra með fordómum (e. static analysis). Það er því mikilvægt að segja kunnugum stríð á hendur með "afhverju?" og "afhverju ekki?" þeir kunna vel að meta sem best eru að sér ... þannig má halda þekkingunni lifandi og leysa vit úr læðingi.

Margur heldur mig sig.