The UvA-LINKER will give you a range of other options to find the full text of a publication (including a direct link to the full-text if it is located on another database on the internet).
De UvA-LINKER biedt mogelijkheden om een publicatie elders te vinden (inclusief een directe link naar de publicatie online als deze beschikbaar is in een database op het internet).

Zoekresultaten

Zoekopdracht: faculteit: "FNWI" en publicatiejaar: "2010"

AuteursH. Buhrman, L. Fortnow, M. Koucký, J.D. Rogers, N. Vereshchagin
TitelDoes the polynomial hierarchy collapse if onto functions are invertible?
TijdschriftTheory of Computing Systems
Jaargang46
Jaar2010
Nummer1
Pagina's143-156
ISSN14324350
FaculteitFaculteit der Natuurwetenschappen, Wiskunde en Informatica
Instituut/afd.FNWI: Institute for Logic, Language and Computation (ILLC)
SamenvattingThe 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 equal UP and TFNP(NP) functions are not computable in polynomial-time with an NP oracle.
Soort documentArtikel
Download
Document finderUvA-Linker