The polynomial and linear time hierarchies in V0 |
| |
| Authors: | Leszek A. Kołodziejczyk Neil Thapen |
| |
| Affiliation: | 1. Institute of Mathematics, University of Warsaw, Banacha 2, 02‐097 Warszawa, Poland;2. Institute of Mathematics, Academy of Sciences of the Czech Republic, ?itná 25, CZ‐115 67 Praha 1, Czech Republic |
| |
| 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) |
| |
| Keywords: | Prefix parity linear hierarchy bounded arithmetic bounded depth circuits |
|
|
