Inverting Onto Functions and Polynomial Hierarchy

Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, J.; Vereshchagin, Nikolay Konstantinovich

H.M. Buhrman (Harry), L. Fortnow (Lance), M. Koucký (Michal), J. Rogers and N.K. Vereshchagin (Nikolay Konstantinovich)

2007-07-01

Inverting Onto Functions and Polynomial Hierarchy

Presented at the International Symposium on Computer Science in Russia, Ekaterinburg, Russia

In this paper we construct an oracle under which the polynomial hierarchy is infinite but there are non-invertible polynomial time computable multivalued onto functions.

Additional Metadata
Keywords	polynomial hierarchy, inverting function, oracles
Publisher	Springer
Editor	V. Diekert , M.V. Volkov , M. Voronkov
Series	Lecture Notes in Computer Science
Project	Quantum Information Processing
Conference	International Symposium on Computer Science in Russia
Organisation	Quantum Computing and Advanced System Research
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Buhrman, H., Fortnow, L., Koucký, M., Rogers, J., & Vereshchagin, N. K. (2007). Inverting Onto Functions and Polynomial Hierarchy. In V. Diekert, M. V. Volkov, & M. Voronkov (Eds.), Lecture Notes in Computer Science (pp. 92–103). Springer.

Free Full Text ( Final Version , 158kb )

Inverting Onto Functions and Polynomial Hierarchy

Publication

Publication

Address

CWI researchers

Questions or comments?

Inverting Onto Functions and Polynomial Hierarchy

Publication

Publication

Workflow

Workflow

Add Content