Number of the records: 1  

Inverting Onto Functions and Polynomial Hierarchy

  1. 1.
    0089758 - MÚ 2008 RIV RU eng C - Conference Paper (international conference)
    Buhrman, H. - Fortnow, L. - Koucký, Michal - Rogers, J.D. - Vereshchagin, N.K.
    Inverting Onto Functions and Polynomial Hierarchy.
    [Invertování projektivních funkcí a polynomiální hierarchie.]
    Proceedings of International Computer Science Symposium in Russia, CSR 2007. Berlin: Springer-Verlag, 2007 - (Diekert, V.; Volkov, M.; Voronkov, A.), s. 92-103. Lecture Notes in Computer Science, 4649. ISBN 978-3-540-74509-9.
    [International Computer Science Symposium in Russia, CSR 2007. Jekaterinburg (RU), 03.09.2007-07.09.2007]
    R&D Projects: GA ČR GA201/05/0124; GA ČR GP201/07/P276
    Institutional research plan: CEZ:AV0Z10190503
    Keywords : one-way functions * polynomial hierarchy * Kolmogorov generic oracles
    Subject RIV: BA - General Mathematics

    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.

    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í.
    Permanent Link: http://hdl.handle.net/11104/0150859

     
    FileDownloadSizeCommentaryVersionAccess
    Koucky1.pdf1211.9 KBPublisher’s postprintrequire
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.