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. |