Počet záznamů: 1

The polynomial and linear time hierarchies in V-0

  1. 1.
    0337059 - MU-W 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
    Grant CEP: GA MŠk 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 souboruStaženoVelikostKomentářVerzePřístup
    Thapen.pdf1208.2 KBVydavatelský postprintvyžádat