Inverting Onto Functions and Polynomial Hierarchy
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F07%3A00089758" target="_blank" >RIV/67985840:_____/07:00089758 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Inverting Onto Functions and Polynomial Hierarchy
Original language description
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? 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. To create the oracle, we introduce Kolmogorov-generic oracles where the strings placed in the oracle are derived from an exponentially long Kolmogorov-random string. We also show that relative to this same oracle, P is not equal to UP and TFNP functions with a SAT oracle are not computable in polynomial-time with a SAT oracle.
Czech name
Invertování projektivních funkcí a polynomiální hierarchie
Czech description
Zabýváme se otázkou, zda invertování funkcí, jejichž hodnota je polynomiálně verifikovatelná, jsou výpočetně těžké. Sestrojíme orákula, kde tomu tak není.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of International Computer Science Symposium in Russia, CSR 2007
ISBN
978-3-540-74509-9
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
92-103
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Jekaterinburg
Event date
Sep 3, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—