"000270961200004" . "55" . "Kolodziejczyk, L.. A." . . "The polynomial and linear time hierarchies in V-0" . "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."@en . . . "334192" . "Mathematical Logic Quarterly" . "The polynomial and linear time hierarchies in V-0"@en . . "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." . . "RIV/67985840:_____/09:00337059" . "DE - Spolkov\u00E1 republika N\u011Bmecko" . "6"^^ . . . "Thapen, Neil" . . "The polynomial and linear time hierarchies in V-0" . "0942-5616" . . . "[9404566CEEC4]" . . "RIV/67985840:_____/09:00337059!RIV10-MSM-67985840" . "The polynomial and linear time hierarchies in V-0"@en . . . . . "5" . "2"^^ . . . . "P(LC505), Z(AV0Z10190503)" . "1"^^ . "Prefix parity; linear hierarchy; bounded arithmetic; bounded depth circuits"@en .