velikost textu

Feasible incompleteness

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Feasible incompleteness
Název v češtině:
Polynominální neúplnost
Typ:
Bakalářská práce
Autor:
Bc. Martin Maxa
Vedoucí:
prof. RNDr. Pavel Pudlák, DrSc.
Oponent:
Mgr. Pavel Hrubeš, Ph.D.
Id práce:
197744
Fakulta:
Filozofická fakulta (FF)
Pracoviště:
Katedra logiky (21-KLOG)
Program studia:
Logika (B6142)
Obor studia:
Logika (LG)
Přidělovaný titul:
Bc.
Datum obhajoby:
19. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
computational complexity|proof complexity|incompleteness
Klíčová slova v angličtině:
computational complexity|proof complexity|incompleteness
Abstrakt:
Abstrakt (£esky): V této práci se zabýváme nitními prot¥j²ky známých v¥t, jeº se týkají základ· matematiky, jako jsou Gödelovy v¥ty o neúplnosti £i Löbova v¥ta. Jejich nitní verze jsou jiº siln¥j²í neº známé otev°ené problémy ve výpo£ní sloºitosti jako nap°. P = NP. Krom¥ nitní verze druhé Gödelovy v¥ty, jeº byla zavedena v práci [1], p°edstavíme i nitní verzy První Gödelovy v¥ty a dokáºeme jejich ekvivalenci. Dále p°edstavíme i n¥které dal²í domn¥nky, jeº jiº implikují nitní verzi První Gödelovy v¥ty a které jsou zajímavé tím, ºe jde o pozitivní tvrzení. Uvedeme navíc tvrzení, jeº by se dalo nazvat nitní verzí Löbovy v¥ty a dokáºeme její vztah k ostatním domn¥nkám. Cílem této práce je ukázat, ºe otev°ené problémy ve výpo£etní sloºitosti mají velmi blízký vztah k problém·m dotýkajících se samých základ· matematiky a logiky a ºe koncept polynomiální dokazatelnosti je podobn¥ d·leºitý koncept jako koncept dokazatelnosti kla- sické. References [1] [1986] P. Pudlák: On the length of proofs of nitistic consistency statements in rst order theories. In: Logic Colloquium 84, North Holland P.C., pp.165-196 1
Abstract v angličtině:
Abstract (in English): We will present in this thesis nite counterparts to the well known theorems that are connected to the foundations of mathematics such as Gödel's incompleteness theorems or Löb's theorem. Their nite versions go already beyond famous open problems in computational theory, for example P = NP. Beside nite version of Gödel's second incompleteness theorem that was introduced in [1], we present also nite version of Gödel's rst incompleteness theorem and we will prove that they are equivalent. Moreover, we present conjectures that are stronger than nite version of Gödel's rst incompleteness theorem and that are interesting as they refer to the positive statements of mathematics. We will also present a conjecture that could be called nite version of Löb's theorem and we will prove relationship of this conjecture to the other conjectures. The aim of this thesis is to show that open problems in computational complexity are closely connected to the problems of the foundations of mathematics and logic and that the concept of polynomial, or we can say feasible, provability is similarly important as is the concept of classical provability. References [1] [1986] P. Pudlák: On the length of proofs of nitistic consistency statements in rst order theories. In: Logic Colloquium 84, North Holland P.C., pp.165-196 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Martin Maxa 358 kB
Stáhnout Abstrakt v českém jazyce Bc. Martin Maxa 63 kB
Stáhnout Abstrakt anglicky Bc. Martin Maxa 52 kB
Stáhnout Posudek vedoucího prof. RNDr. Pavel Pudlák, DrSc. 33 kB
Stáhnout Posudek oponenta Mgr. Pavel Hrubeš, Ph.D. 31 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Vítězslav Švejdar, CSc. 152 kB