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.

---