Nie jesteś zalogowany | Zaloguj się

The polynomial and linear time hierachies in a weak theory of arithmetic

Prelegent(ci)
Leszek Kolodziejczyk
Afiliacja
Uniwersytet Warszawski
Termin
9 stycznia 2008 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

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.