Složenost dokaza u polinomnom računu.

Sažetak: Postoje razni sustavi zaključivanja koji nam omogućavaju da dokažemo da je formula F iz logike sudova antitautologija. Jedan od tih sustava je polinomni račun u kojem formulu F interpretiramo kao sustav polinomnih jednadžbi te provedemo dokazivanje nad polinomima. Prirodno pitanje koje možemo postaviti je koliko veliki moraju biti takvi dokazi. U važnom radu iz 2001. godine, Alekhnovich i Razborov dokazali su da će slučajno odabrana formula propozicionalne logike skoro sigurno imati dokaze eksponencijalne veličine. Bez obzira na njihov rezultat, dokazivanje donjih granica za druge formule ostao je težak problem. Do sada, jedini rad koji je nadogradio originalnu metodu je bio rezultat od Galesija i Laurije iz 2010. godine. U ovom predavanju dat ću skicu originalnog dokaza od Alekhnovicha i Razborova iz 2001. Nakon toga prezentirat ću najnoviju generalizaciju tog rezultata koja obuhvaća i rezultat od Galesija i Laurije, te omogućava dokaze novih donjih granica za veličinu dokaza.