Structural analysis of the complexity of inverse functions

DOI10.1007/BF01202283MaRDI QIDQ4032932zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexity of inverse functionspolynomial-time computable honest functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Inverting onto functions.
• scientific article; zbMATH DE number 58287
• Inverse monoids associated with the complexity class NP
• A survey of one-way functions in complexity theory
• Functional inversion and communication complexity

Cites work

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

Cited in

(15)

• scientific article; zbMATH DE number 176209 (Why is no real title available?)
• Some structural properties of SAT
• Functional inversion and communication complexity
• Computing Inverse ST in Linear Complexity
• Reverse complexity
• Relativized worlds with an infinite hierarchy
• Derandomizing isolation in space-bounded settings
• scientific article; zbMATH DE number 58287 (Why is no real title available?)
• Inverting onto functions.
• On the Inversion Complexity of a System of Functions
• scientific article; zbMATH DE number 6415494 (Why is no real title available?)
• Complexity of inverting the Euler function
• Resource-bounded Kolmogorov complexity revisited
• Asymptotic granularity reduction and its application
• A taxonomy of complexity classes 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)