Structural analysis of the complexity of inverse functions
From MaRDI portal
Publication:4032932
DOI10.1007/BF01202283zbMATH Open0771.68070OpenAlexW2085861229MaRDI QIDQ4032932FDOQ4032932
Authors: Osamu Watanabe, Seinosuke Toda 
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
Recommendations
Cites Work
- The complexity of optimization problems
- NP-hard sets are superterse unless NP is small
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- NP is as easy as detecting unique solutions
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- A comparison of polynomial time completeness notions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Probabilistic quantifiers and games
- On Tally Relativizations of $BP$-Complexity Classes
Cited In (15)
- Complexity of inverting the Euler function
- A taxonomy of complexity classes of functions
- Reverse complexity
- Derandomizing isolation in space-bounded settings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relativized worlds with an infinite hierarchy
- Resource-bounded Kolmogorov complexity revisited
- Computing Inverse ST in Linear Complexity
- Functional inversion and communication complexity
- Asymptotic granularity reduction and its application
- Inverting onto functions.
- Title not available (Why is that?)
- Some structural properties of SAT
- On the Inversion Complexity of a System of Functions
This page was built for publication: Structural analysis of the complexity of inverse functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032932)
