Počet záznamů: 1

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

  1. 1.
    0352519 - MU-W 2011 RIV US eng J - Článek v odborném periodiku
    Buhrman, H. - Fortnow, L. - Koucký, Michal - Rogers, J.D. - Vereshchagin, N.K.
    Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?.
    Theory of Computing Systems. Roč. 46, č. 1 (2010), s. 143-156 ISSN 1432-4350.
    [2nd International Computer Science Symposium in Russia (CSR 2007). Ekaterinburg, 03.09.2007-07.09.2007]
    Grant CEP: GA ČR GP201/07/P276; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: one-way functions * polynomial hierarchy * Kolmogorov generic oracles
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.600, rok: 2010
    http://link.springer.com/article/10.1007%2Fs00224-008-9160-8

    The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P/not=UP and TFNP^NP functions are not computable in polynomial-time with an NP oracle.
    Trvalý link: http://hdl.handle.net/11104/0192010
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky2.pdf1382.5 KBVydavatelský postprintvyžádat