Feasible incompleteness
Thesis title in Czech: | Polynominální neúplnost |
---|---|
Thesis title in English: | Feasible incompleteness |
Key words: | computational complexity|proof complexity|incompleteness |
English key words: | computational complexity|proof complexity|incompleteness |
Academic year of topic announcement: | 2017/2018 |
Thesis type: | Bachelor's thesis |
Thesis language: | angličtina |
Department: | Department of Logic (21-KLOG) |
Supervisor: | prof. RNDr. Pavel Pudlák, DrSc. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 09.11.2017 |
Date of assignment: | 13.11.2017 |
Administrator's approval: | not processed yet |
Confirmed by Study dept. on: | 23.04.2019 |
Date and time of defence: | 19.06.2019 10:00 |
Date of electronic submission: | 07.05.2019 |
Date of proceeded defence: | 19.06.2019 |
Submitted/finalized: | committed by student and finalized |
Opponents: | Mgr. Pavel Hrubeš, Ph.D. |
Guidelines |
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). |
References |
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. |