Nie jesteś zalogowany |
A collapse result for constant depth propositional proof systems with modular counting connectives - continuation
- Prelegent(ci)
- Leszek Kołodziejczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 23 stycznia 2013 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
In the second part of my talk, I would like to discuss in more detail
some issues that were mentioned only briefly in the first part. In
particular, I would like to say some more about:
- the definition of constant depth proof systems, with or without modular counting connectives,
- the correspondence between bounded arithmetic theories and constant depth proof systems,
- the proof of the base case of Toda's theorem (the so-called Valiant-Vazirani lemma), and some issues related to formalizing it in arithmetic.
- the definition of constant depth proof systems, with or without modular counting connectives,
- the correspondence between bounded arithmetic theories and constant depth proof systems,
- the proof of the base case of Toda's theorem (the so-called Valiant-Vazirani lemma), and some issues related to formalizing it in arithmetic.
