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).

Search results

Query: faculty: "FNWI" and publication year: "2010"

AuthorsH. Buhrman, L. Fortnow, M. Koucký, J.D. Rogers, N. Vereshchagin
TitleDoes the polynomial hierarchy collapse if onto functions are invertible?
JournalTheory of Computing Systems
Volume46
Year2010
Issue1
Pages143-156
ISSN14324350
FacultyFaculty of Science
Institute/dept.FNWI: Institute for Logic, Language and Computation (ILLC)
AbstractThe 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.
Document typeArticle
Download
Document finderUvA-Linker