The polynomial and linear time hierarchies in V0
Leszek Aleksander Kołodziejczyk, Neil Thapen · Mathematical logic quarterly · 2009
Abstract We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)