Feasible incompleteness

• Název práce v češtině: Polynominální neúplnost
• Název v anglickém jazyce: Feasible incompleteness
• Klíčová slova: computational complexity|proof complexity|incompleteness
• Klíčová slova anglicky: computational complexity|proof complexity|incompleteness
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra logiky (21-KLOG)
• Vedoucí / školitel: prof. RNDr. Pavel Pudlák, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.11.2017
• Datum zadání: 13.11.2017
• Schválení administrátorem: zatím neschvalováno
• Datum potvrzení stud. oddělením: 23.04.2019
• Datum a čas obhajoby: 19.06.2019 10:00
• Datum odevzdání elektronické podoby: 07.05.2019
• Datum proběhlé obhajoby: 19.06.2019
• Odevzdaná/finalizovaná: odevzdaná studentem a finalizovaná
• Oponenti: Mgr. Pavel Hrubeš, Ph.D.

Zásady pro vypracování

Student se seznámí s dostupnou literaturou a zpracuje téma formou "učebního" textu (t.j. vypracuje text vhodný jako úvod pro logiky, kteří však nejsou odborníci v oblasti výpočetní složitosti).

Seznam odborné literatury

Pudlák, Pavel: Incompleteness in the finite domain
Pudlák, Pavel: Logical Foundations of Mathematics and Computational Complexity a gentle introduction
Cook, Steven A.: Feasibly constructive proofs and the propositional calculus, Proc. of 7th annual ACM symposium on Theory of computing, Albuerque, New Mexico, pp.83-97, (1975)
Krajíček. Jan a Pudlák, Pavel Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations, J. Symbolic Logic, 54(3), (1989), pp. 1063-1079.