Bounded arithmetic and complexity theory

• Název práce v češtině: Omezená aritmetika a teorie složitosti
• Název v anglickém jazyce: Bounded arithmetic and complexity theory
• Klíčová slova: omezená aritmetika|teorie složitosti|teorie modelů
• Klíčová slova anglicky: bounded arithmetic|complexity theory|model theory
• Akademický rok vypsání: 2021/2022
• 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í: 02.08.2022
• Datum zadání: 02.08.2022
• Datum potvrzení stud. oddělením: 08.09.2022

Zásady pro vypracování

Bounded arithmetic and computational complexity

Bounded arithmetic and computational complexity are
related in a number of ways, e.g. witnessing theorems
or complexity of propositional logic. In particular, open
problems about provability of various counting principles
valid for finite sets in bounded arithmetic are intimately
related to problems around the polynomial hierarchy. The
task is to contribute to this area some original results.

Seznam odborné literatury

M.Ajtai, Parity and the pigeonhole principle,
in: Feasible Mathematics, eds. S.R.Buss and P.J.Scott,
(1990), pp.1-24. Birkhauser.

J.Krajicek, Bounded arithmetic, propositional
logic, and complexity theory, Cambridge University Press,
(1995).

J.Krajicek, Proof complexity, Cambridge University Press,
(2019).

J.Paris and A.J.Wilkie, Counting problems in bounded arithmetic,
in: Methods in Mathematical Logic, LN in Mathematics, 1130,
(1985), pp.317-340. Springer-Verlag.

J.Paris, A.J.Wilkie and A.Woods, Provability of the Pigeonhole
Principle and the Existence of Infinitely Many Primes,
J. of Symbolic Logic, 53(4), (1988), pp.1235-1244.

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

Relations between bounded arithmetic and computational complexity.

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

Relations between bounded arithmetic and computational complexity.