Invertování projektivních funkcí a polynomiální hierarchie

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Inverting Onto Functions and Polynomial Hierarchy

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Inverting Onto Functions and Polynomial Hierarchy

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of International Computer Science Symposium in Russia, CSR 2007

ISBN

978-3-540-74509-9

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

92-103

Název nakladatele

Springer-Verlag

Místo vydání

Berlin

Místo konání akce

Jekaterinburg

Datum konání akce

3. 9. 2007

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—