Počet záznamů: 1
The polynomial and linear time hierarchies in V-0
- 1.0337059 - MÚ 2010 RIV DE eng J - Článek v odborném periodiku
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
Grant CEP: GA MŠMT LC505
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Prefix parity * linear hierarchy * bounded arithmetic * bounded depth circuits
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.523, rok: 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.
Trvalý link: http://hdl.handle.net/11104/0181147
Název souboru Staženo Velikost Komentář Verze Přístup Thapen.pdf 1 208.2 KB Vydavatelský postprint vyžádat
Počet záznamů: 1