You are not logged in |
The polynomial and linear time hierachies in a weak theory of arithmetic
- Speaker(s)
- Leszek Kolodziejczyk
- Affiliation
- Uniwersytet Warszawski
- Date
- Jan. 9, 2008, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
I will show that a very weak theory of arithmetic associated with the complexity class AC^0 does not prove that the polynomial time hierarchy is equal to the linear time hierarchy. The proof uses Ajtai's old bounds on how well polysize bounded depth circuits can compute parity.
