text size

Feasible incompleteness

Notice: I hereby declare that I am aware that the information acquired from theses published by Charles University may not be used for commercial purposes or may not be published for educational, scientific or other creative activities as activities of person other than the author.
Title:
Feasible incompleteness
Title (in czech):
Polynominální neúplnost
Type:
Bachelor's thesis
Author:
Bc. Martin Maxa
Supervisor:
prof. RNDr. Pavel Pudlák, DrSc.
Opponent:
Mgr. Pavel Hrubeš, Ph.D.
Thesis Id:
197744
Faculty:
Faculty of Arts (FF)
Department:
Department of Logic (21-KLOG)
Study programm:
Logic (B6142)
Study branch:
Logic (LG)
Degree granted:
Bc.
Defence date:
19/06/2019
Defence result:
Excellent
Language:
English
Keywords (in czech):
computational complexity|proof complexity|incompleteness
Keywords:
computational complexity|proof complexity|incompleteness
Abstract (in czech):
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:
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
Documents
Download Document Author Type File size
Download Text of the thesis Bc. Martin Maxa 358 kB
Download Abstract in czech Bc. Martin Maxa 63 kB
Download Abstract in english Bc. Martin Maxa 52 kB
Download Supervisor's review prof. RNDr. Pavel Pudlák, DrSc. 33 kB
Download Opponent's review Mgr. Pavel Hrubeš, Ph.D. 31 kB
Download Defence's report doc. RNDr. Vítězslav Švejdar, CSc. 152 kB