Number of the records: 1
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
- 1.
SYSNO ASEP 0352519 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Author(s) Buhrman, H. (NL)
Fortnow, L. (US)
Koucký, Michal (MU-W) RID, SAI, ORCID
Rogers, J.D. (US)
Vereshchagin, N.K. (RU)Source Title Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 46, č. 1 (2010), s. 143-156Number of pages 14 s. Action 2nd International Computer Science Symposium in Russia (CSR 2007) Event date 03.09.2007-07.09.2007 VEvent location Ekaterinburg Country RU - Russian Federation Event type WRD Language eng - English Country US - United States Keywords one-way functions ; polynomial hierarchy ; Kolmogorov generic oracles Subject RIV BA - General Mathematics R&D Projects GP201/07/P276 GA ČR - Czech Science Foundation (CSF) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000272912800009 EID SCOPUS 72249101979 DOI 10.1007/s00224-008-9160-8 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2011
Number of the records: 1