Number of the records: 1
The polynomial and linear time hierarchies in V-0
- 1.
SYSNO ASEP 0337059 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title The polynomial and linear time hierarchies in V-0 Title Polynomiální a lineární hierarchie ve V-0 Author(s) Kolodziejczyk, L. A. (PL)
Thapen, Neil (MU-W) RID, SAISource Title Mathematical Logic Quarterly. - : Wiley - ISSN 0942-5616
Roč. 55, č. 5 (2009), s. 509-514Number of pages 6 s. Language eng - English Country DE - Germany Keywords Prefix parity ; linear hierarchy ; bounded arithmetic ; bounded depth circuits Subject RIV BA - General Mathematics R&D Projects LC505 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000270961200004 DOI 10.1002/malq.200810007 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2010
Number of the records: 1