A taxonomy of complexity classes of functions

DOI10.1016/S0022-0000(05)80009-1zbMath0806.68049MaRDI QIDQ1329166

Selman, Alan L.

Publication date: 13 February 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

taxonomypartial multivalued functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (42)

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ Probabilistic logic under coherence: complexity and algorithms ⋮ UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Functions computable with limited access to NP ⋮ Reductions between disjoint NP-pairs ⋮ Cluster computing and the power of edge recognition ⋮ Expressive probabilistic description logics ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Average-case intractability vs. worst-case intractability ⋮ The isomorphism problem for finite extensions of free groups is in PSPACE ⋮ Unnamed Item ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The Shrinking Property for NP and coNP ⋮ Pseudorandom generators against advised context-free languages ⋮ The shrinking property for NP and coNP ⋮ Foundations of probability-raising causality in Markov decision processes ⋮ Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results ⋮ The consequences of eliminating NP solutions ⋮ On the complexity of core, kernel, and bargaining set ⋮ Inverting onto functions. ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ On quasilinear-time complexity theory ⋮ Computing functions with parallel queries to NP ⋮ Federation and Navigation in SPARQL 1.1 ⋮ Graph Isomorphism is in SPP ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Complexity classes of equivalence problems revisited ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ A hierarchy based on output multiplicity ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly ⋮ Do there exist complete sets for promise classes? ⋮ Černý's conjecture and the road colouring problem ⋮ Theory of one-tape linear-time Turing machines ⋮ Some structural properties of SAT ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ Resource bounded immunity and simplicity ⋮ On the complexity of data disjunctions. ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ On the query complexity of selecting minimal sets for monotone predicates ⋮ Reducing the number of solutions of NP functions ⋮ Complexity results for explanations in the structural-model approach

Cites Work

• Unnamed Item
• NP is as easy as detecting unique solutions
• The complexity of optimization problems
• Relative complexity of checking and evaluating
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Bounded Query Classes
• The complexity of promise problems with applications to public-key cryptography
• Quantitative Relativizations of Complexity Classes
• The difference and truth-table hierarchies for NP
• Complexity Measures for Public-Key Cryptosystems
• Natural Self-Reducible Sets
• A survey of one-way functions in complexity theory
• Structural analysis of the complexity of inverse functions
• Polynomial Time Enumeration Reducibility
• P-Printable Sets
• The complexity of theorem-proving procedures
• On the power of parity polynomial time

This page was built for publication: A taxonomy of complexity classes of functions