Bounded arithmetic and complexity theory

• Thesis title in Czech: Omezená aritmetika a teorie složitosti
• Thesis title in English: Bounded arithmetic and complexity theory
• Key words: omezená aritmetika|teorie složitosti|teorie modelů
• English key words: bounded arithmetic|complexity theory|model theory
• Academic year of topic announcement: 2021/2022
• Thesis type: dissertation
• Thesis language: angličtina
• Department: Department of Algebra (32-KA)
• Supervisor: prof. RNDr. Jan Krajíček, DrSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 02.08.2022
• Date of assignment: 02.08.2022
• Confirmed by Study dept. on: 08.09.2022

Guidelines

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.

References

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.

Preliminary scope of work

Relations between bounded arithmetic and computational complexity.

Preliminary scope of work in English

Relations between bounded arithmetic and computational complexity.