Inverting Onto Functions and Polynomial Hierarchy

DOI10.1007/978-3-540-74510-5_12MaRDI QIDQ3499770zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Michal Koucký, John D. Rogers, Lance Fortnow, Nikolai K. Vereshchagin

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/12112

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Does the polynomial hierarchy collapse if onto functions are invertible?
• Towards a unified complexity theory of total functions
• The journey from NP to TFNP hardness
• Functions computable with limited access to NP
• scientific article; zbMATH DE number 58287

Cited in

(8)

• A taxonomy of complexity classes of functions
• Inverting onto functions.
• The polynomial hierarchy of functions and its levels
• On average-case hardness in \textsf{TFNP} from one-way functions
• Does the polynomial hierarchy collapse if onto functions are invertible?
• The Shrinking Property for NP and coNP
• The journey from NP to TFNP hardness
• The shrinking property for NP and coNP

This page was built for publication: Inverting Onto Functions and Polynomial Hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499770)