Počet záznamů: 1
The polynomial and linear time hierarchies in V-0
- 1.
SYSNO ASEP 0337059 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název The polynomial and linear time hierarchies in V-0 Překlad názvu Polynomiální a lineární hierarchie ve V-0 Tvůrce(i) Kolodziejczyk, L. A. (PL)
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Mathematical Logic Quarterly. - : Wiley - ISSN 0942-5616
Roč. 55, č. 5 (2009), s. 509-514Poč.str. 6 s. Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova Prefix parity ; linear hierarchy ; bounded arithmetic ; bounded depth circuits Vědní obor RIV BA - Obecná matematika CEP LC505 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000270961200004 DOI 10.1002/malq.200810007 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1