Structural analysis of the complexity of inverse functions

DOI10.1007/BF01202283zbMath0771.68070OpenAlexW2085861229MaRDI QIDQ4032932

Seinosuke Toda, Osamu Watanabe

Publication date: 17 May 1993

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202283

zbMATH Keywords

complexity of inverse functionspolynomial-time computable honest functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

A taxonomy of complexity classes of functions ⋮ Resource-bounded kolmogorov complexity revisited ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Some structural properties of SAT ⋮ Relativized worlds with an infinite hierarchy

Cites Work

• NP-hard sets are superterse unless NP is small
• NP is as easy as detecting unique solutions
• A comparison of polynomial time completeness notions
• The complexity of optimization problems
• Probabilistic quantifiers and games
• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• On Tally Relativizations of $BP$-Complexity Classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

This page was built for publication: Structural analysis of the complexity of inverse functions