The polynomial and linear time hierarchies in V-0

0337059 - MÚ 2010 RIV DE eng J - Journal Article
Kolodziejczyk, L. A. - Thapen, Neil
The polynomial and linear time hierarchies in V-0.
[Polynomiální a lineární hierarchie ve V-0.]
Mathematical Logic Quarterly. Roč. 55, č. 5 (2009), s. 509-514. ISSN 0942-5616. E-ISSN 1521-3870
R&D Projects: GA MŠMT LC505
Institutional research plan: CEZ:AV0Z10190503
Keywords : Prefix parity * linear hierarchy * bounded arithmetic * bounded depth circuits
Subject RIV: BA - General Mathematics
Impact factor: 0.523, year: 2009

We show that the bounded arithmetic theory V-0 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.

Ukážeme, že omezená aritmetická teorie V0 nedokazuje, že polynomiální hierarchie kolapsuje na lineární hierarchii.
Permanent Link: http://hdl.handle.net/11104/0181147