You are not logged in | Log 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.