Název:
Výsledky o (ne)možnostech v důkazové složitosti a aritmetice
Překlad názvu:
(Im)possibilty results in Proof Complexity and Arithmetic
Autoři:
Khaniki, Erfan ; Pudlák, Pavel (vedoucí práce) ; Buss, Samuel (oponent) ; Kolodziejczyk, Leszek (oponent) Typ dokumentu: Disertační práce
Rok:
2023
Jazyk:
eng
Abstrakt: [eng][cze] Title: (Im)possibilty results in Proof Complexity and Arithmetic Author: Erfan Khaniki Department: Department of Algebra Supervisor: Prof. RNDr. Pavel Pudl'ak, DrSc Abstract: We study various problems in proof complexity, bounded arithmetic, and intuitionistic arithmetic. We focus on topics such as lower bounds for different proof systems, connections between proof complexity generators and models of arithmetic, jump operators in proof complexity, and the non-locality of certain Kripke models of Heyting arithmetic. Keywords: Proof complexity, Lower bounds, Bounded arithmetic, Independence, Heyt- ing arithmetic, Kripke models 1Názov práce: Výsledky o (ne)možnostech v důkazové složitosti a aritmetice Autor: Erfan Khaniki Katedra: Katedra Algebry Vedúci dizertačnej práce: Prof. RNDr. Pavel Pudlák, DrSc Abstrakt: Zabýváme se problémy v důkazové složitosti, omezené aritmetice a intu- icionistické aritmetice. Soustředíme se na témata jako dolní odhady pro různé důkazové systémy, souvislosti mezi generátory v důkazové složitosti a modely ar- itmetiky, operátory skoku v důkazové složitosti a nelokalitou určitých Kripkeho modelů v Heytingově aritmetice. Klíčová slova: důkazová složitost, dolní odhady, omezenená aritmetika, nezávislost, Heytin- gova aritmetika, Kripkeho modely 1
Klíčová slova:
důkazová složitost|dolní odhady|omezenená aritmetika|nezávislost|Heytingova aritmetika|Kripkeho modely; Proof complexity|Lower bounds|Bounded arithmetic|Independence|Heyting arithmetic|Kripke models