Počet záznamů: 1
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
- 1.
SYSNO ASEP 0352519 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 Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Tvůrce(i) Buhrman, H. (NL)
Fortnow, L. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Rogers, J.D. (US)
Vereshchagin, N.K. (RU)Zdroj.dok. Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 46, č. 1 (2010), s. 143-156Poč.str. 14 s. Akce 2nd International Computer Science Symposium in Russia (CSR 2007) Datum konání 03.09.2007-07.09.2007 Místo konání Ekaterinburg Země RU - Rusko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova one-way functions ; polynomial hierarchy ; Kolmogorov generic oracles Vědní obor RIV BA - Obecná matematika CEP GP201/07/P276 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000272912800009 EID SCOPUS 72249101979 DOI 10.1007/s00224-008-9160-8 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1