Proof Complexity of CSP

• Název práce v češtině: Důkazová složitost CSP
• Název v anglickém jazyce: Proof Complexity of CSP
• Klíčová slova: omezená aritmetika|problém splňování podmínek|důkazová složitost|univerzální algebra
• Klíčová slova anglicky: bounded arithmetic|constraint satisfaction problem|proof complexity|universal algebra
• Akademický rok vypsání: 2018/2019
• Typ práce: disertační práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 27.09.2018
• Datum zadání: 27.09.2018
• Datum potvrzení stud. oddělením: 29.10.2018
• Datum a čas obhajoby: 20.02.2024 14:00
• Datum odevzdání elektronické podoby: 01.10.2023
• Datum odevzdání tištěné podoby: 09.10.2023
• Datum proběhlé obhajoby: 20.02.2024
• Oponenti: prof. Antonina Kolokolova

Zásady pro vypracování

To prove a new result in the area of proof complexity.

Seznam odborné literatury

Proof Complexity, Cambridge U. Press, to app.,
draft available at: http://www.karlin.mff.cuni.cz/~krajicek/prfdraft.html

Předběžná náplň práce

Viz. anglická upoutávka.

Předběžná náplň práce v anglickém jazyce

Proof complexity is an area connecting mathematical logic and computational complexity
theory. The main problem is whether the class NP is closed under complementation. There are
many probably more accesible open problems.