Malá analýza poznania

JAZYK je dany slovami a pravidlami ich pouzivania
vyznam slov je dany suvislostiami v akych su pouzivane

1 MOJ SVET je MOJ JAZYK
kazdy jav moze byt jednoznacne oznaceny slovom
kazdy jav moze byt jednoznacne popisany suvislostiami v akych su
prislusne slova pouzivane s inymi slovami
javy o ktorych sa neda hovorit neexistuju
o com sa neda hovorit o tom treba mlcat

je efektivne rozhodnutelne co je a co nie je slovo, tvrdenie ci korektna
dedukcia
nerekurzivnost je slovo rekurzivneho jazyka/nekonecno je slovo
konecneho jazyka

2 ZMYSLUPLNE OTAZKY maju ZMYSLUPLNE ODPOVEDE
otazka/tvrdenie je spravne polozena ak odpoved na nu/jeho pravdivost
je mozne overit (tj overit efektivne)
tvrdenia ktorych pravdivost nie je mozne overit su redundantne a
nezmyselne tvrdenia o tomto svete

3 EFEKTIVNY ALGORITMUS odpovedajuci na otazky s efektivne verifikovatelnou
odpovedou odpoveda na vsetky otazky

Po zodpovedani vsetkych vedeckych otazok neostanu ziadne otazky

Neexistuje osud nad ktory by sa nedalo povzniest

Nisan-Wigderson generators in proof systems with forms of interpolation

The NW-generators based on computationally hard functions and suitable matrices are hard for proof systems that admit feasible interpolation. You can find the proof here.

Fernando Pessoa: obchod tabaku

Clarissa Vaughn: He gives me that look.
Julia: What look?
Clarissa Vaughn: To say your life is trivial. You are so trivial.
the hours

dan mangan – the indie queens are waiting

par usekov najslavnejsej pessoaovej basne “tobacco shop” (bohuzial som nenasiel ziaden preklad, cela basen tu):

…
Today I am defeated, as if I knew the truth.
Today I am clear-minded, as if I were about to die
And had no greater kinship with things
Than to say goodbye, this building and this side of the street becoming
A row of train cars, departing at the sound of a whistle
Blowing from inside my head,
And a jolt to my nerves and a creak of bones as we go.

FOM2.1: Dôôkazové systémy, Generátory dôkazovej zložitosti

..the best mathematician is the one who see the deepest..

House: Now we’re getting somewhere.
Foreman: Where?
House: I have no idea.

muse-the resistance [full new album, futuristic rock, tip: exogenesis symphony]

Po tom co sme sformalizovali matematiku, ujasnili pojmy ako pravda, dokazanie pravdivosti a ukazali ze formalne systemy prakticky nevyhnutne trpia znacnou mierou neuplnosti, sme si povedali ze by bolo skvele ak by nase systemy dokazovali pravdive teoremy navyse tak aby slo lahko zistit ktore tvrdenia dokazuju (hoci i pomocou pocitacov). Najoptimistickejsie sme to formulovali ako P=NP tvrdenie: “zistit ze dane tvrdenie ma dokaz dlzky n (v akejkolvek beznej teorii) vie pocitac efektivne”. Presvedcenie ze tak ocividnu nepravdu o zviazani matematiky do moci masin lahko poprieme vsak zlyhava. P vs NP problem zaradeny medzi tie najdolezitejsie v matematike stale caka na riesenie.

P vs NP je symbol snahy zistit co je efektivne riesitelne v nasom svete (ina pekna metafora: aky zlozity je tento svet). To bezohladu na to ze formalisticky vzate nam v tom jeho riesenie nemusi pomoct.
Dolezitou vetvou tohto vyskumu je dokazova zlozitost. Ta skuma ake dokazove systemy su potrebne na efektivne dokazovanie roznych matematickych tvrdeni.

Je zvykom skumat dokazove systemy vyrokovych tautologii, do ktorych mozno vacsinu zaujimavych veci prelozit. Napriklad tvrdenia typu , kde neobsahuje neobmedzeny kvantifikator, ako riemannova hypoteza ci sa daju vyjadrit sekvenciami vyrokovych formul. Mimochodom sa tak mozme napr pytat ci formule tvrdiace ze existuje tazke tvrdenie () su tazke pre dane dokazove systemy. To ze tvrdenie nema kratke dokazy vo vyrokovom systeme tiez casto znamena ze je nezavisle na istych teoriach prveho radu.

Dokazova zlozitost vyrokovych tautologii je vsak zaujimava i z fundamentalnejsich dovodov. Ak ma platit P=NP je nutne aby existoval dokazovy system s kratkymi dokazmi tautologii. Jeho existencia je pritom ekvivalentna tvrdeniu NP=coNP. A pretoze prikladom coNP-uplneho problemu je mnozina , jeho existencia by tiez znamenala ze je mozne dokazovat neexistenciu dokazu dlzky n efektivnejsie nez overenim vsetkych moznych dokazov dlzky n.

Tieto fakty v clanku popiseme exaktnejsie. Zamerame sa potom na generatory dokazovej zlozitosti. Tie predstavuju kandidatov na tazko dokazatelne tautologie. Okrem toho ze iniciuju vyskum generatorov v kontexte dokazovych systemov, v specialnych pripadoch navyse koduju tvrdenia o spodnych odhadoch na booleove funkcie ako co ich robi este atraktivnejsimi.

Kvantové počítače, Shorov algoritmus faktorizácie

As Gregor Samsa awoke one morning from uneasy dreams he found himself transformed in his bed into a gigantic vermin. Franz Kafka, the metamorphosis

drawn inwards – center of the universe/vicelord

Kvantove pocitace predstavuju vyzvu nasej predstave toho co je efektivne vypocitatelne v realnom svete. Pokusaju sa vyuzit jav superpozicie objektu, ako isty druh paralelneho pocitania. Vieme ze ak by take pocitace existovali dokazali by rychlo riesit ulohy ktore s klasickymi pocitacmi dnes efektivne riesit nevieme. Nevieme vsak ani o tom aby priroda vedela riesit NP-problemy efektivne (akymokolvek dejom ktory v nej prebieha) (co mimochodom evokuje kacirsku predstavu ze tak priamo apelujeme na evoluciu k vzniku akejsi superinteligencie).

Rozdiel medzi kvantovym a klasickym pocitacom

Klasicky pocitac sa v kazdom kroku nachadza v nejakom konkretnom stave postupnosti nul a jedniciek kde . Stav pravdepodobnostneho modelu pocitaca charakterizujeme ako sumu kde , , pritom je pravdepodobnost ze sa pocitac nachadza v stave . Kvantovy pocitac sa v kazdom kroku nachadza v stave (superpozicii stavov) kde , a je pravdepodobnost ze sa pocitac pri pozreti sa nan nachadza v stave . Hodnoty nazyvame amplitudy a fakt ze to nie su len kladne cisla je klucovy. Kvantovy pocitac moze aplikovat len tzv elementarne kvantove operacie: Elementarna kvantova operacia na m-bitovy register (ktory je teda v superpozicii stavov tvaru ) je kazda linearna funkcia (operuje na superpozicii m-tic) zobrazujuca jednotkove vektory v znova na jednotkove (unitarita), ktora meni nanajvys tri zlozky tychto vektorov (tzv qbity registra).

K volbe definicie sa hodi odovodnenie. Mne osobne staci nasledujuca intuitivna predstava o fyzike nasho vesmiru: Linearita transformacii vychadza z poziadavok kvantoveho popisu sveta, zhruba povedane, vsetky “pozorovane transformacie” roznych javov (reprezentovanych vektormi) su linearne (na priestore tych vektorov), co mi pride vcelku prekvapujuce. Da sa dokonca ukazat ze ak by sme pripustili nelinearnost slo by riesit NP-ulohy efektivne. Divne ziskana pravdepodobnost umocnenim amplitudy je z casti dosledkom linearity: ak by sme ju totiz chceli definovat vseobecnejsie napr ako pre stav , zistili by sme ze netrivialne linearne transformacie takeho settingu umoznuju len volby (klasicka prst) a (kvant). Dovod pre komplexne cisla je znova poziadavka teorie. Chceme aby mala kazda operacia odmocninu, co je dosledok spojitosti casu v ktorom sa transformacie mozu vyvijat – aplikovat. Hm, dalej uz budeme radsej pracovat len v matematike 🙂

Univerzálna cibuľa

Postmodernists believe that truth is myth, and myth, truth. This equation has it roots in pop psychology. The same people also believe that emotions are a form. Brad Holland

leto nahromadilo par zvesti. najprv chcem upozornit na videa prednasok T.Gowersa, pekne rozprava napr. o prirodzenych dokazoch alebo shorovom algoritme. projekty the Tricki, Polymath (hromadne riesenie otvorenych problemov), Euclid – perspectives in logic a Euclid – lecture notes in logic kde najdete o.i. zdarma knihu hajeka a pudlaka o metamatematike aritmetiky), aka je skoda ked je mlady nadany vedec ako Alekhnovich vlastne mrtvy, Martinov clanok o postaveni Godelovych viet v matematike pre tych ktori im chcu hlbsie rozumiet. videa prednasok workshopu Barriers in Complexity, ktore sa o chvilu objavia niekde tu.

dalej som vymyslel skomoleniny P vs WC, expander razborov a zhodol sa na tom ze by bolo vtipne mat rebelantske tricko s nadpisom “wear rhetoric others will judge you by”, ale pre atmosferu leta bude lepsie najst nejaku dobru hudbu. bohuzial wordpress sam o sebe zda sa nepodporuje youtube playlisty, takze tu tych par tragickych songov, na ktore som narazil, proste nalinkujem.

“free and easy, gentle, gentle.. the wind through the trees makes you mental, for me” uplne letny, viac poeticky nez hudobny, osemminutovy song destroyer – bay of pigs. trocha blaznivejsie osemminutove “nieco” dan deacon – snookered. epicke potemkinovske videa k barokovemu roku arcade fire – intervention. agonicky prejav penningtona z paranthetical girls – stolen children. tiez silne zive vystupenia skusenych indie alter rockovych the strokes ci metric. a trocha vzdy aktualnej klasiky: delibes, prokofiev, debussy. to vsetko a k tomu mramorova ľalia zdarma v tomto playliste

na zaver stanovujem status dying a povinny kus poezie

The Metaphysicians of South Jersey
Stephen Dunn

Because in large cities the famous truths
already had been plumbed and debated,
the metaphysicians of South Jersey lowered
their gaze, just tried to be themselves.
They’d gather at coffee shops in Vineland
and deserted shacks deep in the Pine Barrens.
Nothing they came up with mattered
so they were free to be eclectic, and as odd
as getting to the heart of things demanded.
They walked undisguised on the boardwalk.
At the Hamilton Mall they blended
with the bargain-hunters and the feckless.
Almost everything amazed them,
the last hour of a county fair,
blueberry fields covered with mist.
They sought the approximate weight of sadness,
its measure and coloration. But they liked
a good ball game too, well pitched, lots of zeros
on the scoreboard. At night when they lay down,
exhausted and enthralled, their spouses knew
it was too soon to ask any hard questions.
Come breakfast, as always, the metaphysicians
would begin to list the many small things
they’d observed and thought, unable to stop talking
about this place and what a world it was.

Konceptuálna poézia a tak

it is cold, mechanical, conceptual bullshit. Kim Howells

umenie mava kratku zivotnost. rychlo sa stava pateticke a osuchane. ironia vitazi. asi len ta sa neda zosmiesnit. to vsak neznamena ze si dnes nemozme dat trocha burania klasickych estetickych noriem v podani konceptualnej poezie. ta je paradoxne postavena na neoriginalnosti. ako to uz byva, chce vyzvat k prehodnoteniu toho co sa da nazvat umenim. odpoved zavisi na jednotlivcovi alebo na ministrovi kultury.

niektore kusky su skutocne vtipne. napadlo vas napriklad niekedy usporiadat prvych tisic cisel do alfabetickeho poradia? 🙂 mne to teda nepride prave ako vyjadrenie emocionalnej pravdy ale musim uznat ze to je uderny a chytlavy druh odmietnutia klise citovych vylevov.

acconci, read this word

READ THIS WORD THEN READ THIS WORD READ THIS WORD NEXT READ THIS
WORD NOW SEE ONE WORD SEE ONE WORD NEXT SEE ONE WORD NOW AND
THEN SEE ONE WORD AGAIN LOOK AT THREE WORDS HERE LOOK AT THREE
WORDS NOW LOOK AT THREE WORDS NOW TOO TAKE IN FIVE WORDS AGAIN
TAKE IN FIVE WORDS SO TAKE IN FIVE WORDS DO IT NOW SEE THESE WORDS
AT A GLANCE SEE THESE WORDS AT THIS GLANCE AT THIS GLANCE HOLD THIS
LINE IN VIEW HOLD THIS LINE IN ANOTHER VIEW AND IN A THIRD VIEW SPOT
SEVEN LINES AT ONCE THEN TWICE THEN THRICE THEN A FOURTH TIME A FIFTH
A SIXTH A SEVENTH AN EIGHTH

baldessari, I will not make any more boring art. I will not make any more boring art. ..

nakoniec chutovka:

morris, a method for sorting cows

cisty existencializmus 🙂

vseobecne, sila vyjadrovania takychto “absurdnych” umeleckych smerov moze byt velmi ucinna. veci ktore neviete zasadit do logickej konstrukcie prirodzeneho jazyka, mnohe neurcitosti pocitov,  sa mozu velmi exaktne a vystihujuco prejavit v zhluku divne znejucich navonok nahodnych slov. vhodne narusenie i formalnych barier je asi vec instinktu. a je, da sa povedat, nevyhnutne. vyjadrit sa elegantne je proste priorita.

Fragments of arithmetic that cannot prove superpolynomial circuit lower bounds

When a thing has been said well, have no scruple. Take it and copy it. Anatole France

I have finished my bachelor thesis. Unfortunately, there is not any new result, just one strange little modification of a proof of an interpolation theorem. I hope somebody find it useful. The topic is definitely interesting:

Abstract: We present a known result that the bounded arithmetic theory cannot separate complexity classes P from NP by proving circuit lower bounds unless hard pseudorandom generators do not exist. This was originaly proved by Razborov [17] but we present a simplyfied proof by Krajíček [12].

NP=PCP(log n,1)

Blaise Pascal: We know the truth, not only by the reason, but also by the heart

Tzv PCP teorema je jednym z najuzasnejsich vysledkov teorie zlozitosti. Dava nam polynomialny algoritmus ktory pre dane tvrdenie a nejaky jeho dokaz dlzky n rozhoduje ci je tento dokaz spravny s lubovlne velkou presnestou, tak ze sa pozrie nanajvys na konstantne vela symbolov tohto dokazu a za behu si este asi log n krat hodit ferovou mincou podla ktorej sa zachova.

Znamena to napriklad ze ak ste Boh a dokazete Riemannovu hypotezu, tak nas obycajnych ludi mozete s lubovolne velkou istotou presvedcit o spravnosti vasho dokazu bez toho aby ste nam ukazal viac ako povedzme 20 bitov tohto dokazu. Neuveritelne utajenie.

Finta je v tom ze proces presviedcania je vlastne konstrukciou noveho dokazu. Konieckoncov polynomialny algoritmus pre NP-uplne ulohy by sme v tomto pripade povazovali za proces presviedcania ktory sa nepozrie na dany dokaz vobec a overi ci je skutocne pravda ze dane tvrdenie je dokazatelne v n krokoch polynomialne rychlo. Lenze taky algoritmus mozno vobec neexistuje.

Tiez z hladiska dokazovej zlozitosti PCP teorema vlastne tvrdi ze existuje dokazovy system ktoreho dokazy su rychlo pravdepodobnostne overitelne len konstantnym poctom pozreti na ne. To dava novy pohlad na pojem dokazu. Ten musel byt doteraz overitelny krok po kroku sadou jednoduchych pravidiel.

Takze sa pozrime lepsie kde sa deje ten zazrak. Dokaz PCP teoremy je sice dlhy ale clovekom overitelny, iny by som v tomto pripade asi ani neakceptoval.

Dnes uvedieme len zakladne definicie, (cely) dokaz slabsej verzie PCP teoremy a strukturu dokazu silnej verzie. Cerpam zo skvelych skript Sanjeeva Aroru a Boaza Baraka. online je len neuplny draft, ale dik i za ten.

Filozoficko historický pohľad na P vs NP

I saw the best minds of my generation, destroyed by madness, starving hysterical naked.. Ginsberg(Howl)

..it does not feel like anything to be a vegetable… Wittgenstein vo filme Wittgenstein

Ked sa divame na svet, snazime sa ho pochopit tym ze ho popisujeme matematickymi teoriami. Uz Leibniz si ale uvedomoval ze akokolvek zlozity system mozno popisat dostatocne zlozitou teoriou. Preto je prave jednoduchost meritkom kvality teorie a nevyhnutnostou k pochopeniu systemu ktory popisuje.

Kedy povazujeme teoriu za jednoduchu? Iste by mala byt dana nejakou malou mnozinou axiomov a par odvodzovacimi pravidlami. Navyse by sa nam vsak velmi hodilo aby davala primerane kratke dokazy svojich tvrdeni. Inak sa jej dosledky vlastne nikdy nedozvieme.

SUVISIACE ODKAZY: SKVELA POPULARIZACNA PREDNASKA OD WIGDERSONA, A ESTE LEPSI JEHO PREHLADOVY CLANOK