A taxonomy of complexity classes of functions
From MaRDI portal
Recommendations
Cites work
- A survey of one-way functions in complexity theory
- Bounded Query Classes
- Complexity Measures for Public-Key Cryptosystems
- scientific article; zbMATH DE number 3858857 (Why is no real title available?)
- Natural Self-Reducible Sets
- NP is as easy as detecting unique solutions
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- On the power of parity polynomial time
- P-Printable Sets
- Polynomial Time Enumeration Reducibility
- Quantitative Relativizations of Complexity Classes
- Relative complexity of checking and evaluating
- Structural analysis of the complexity of inverse functions
- The complexity of optimization problems
- The complexity of promise problems with applications to public-key cryptography
- The complexity of theorem-proving procedures
- The difference and truth-table hierarchies for NP
Cited in
(52)- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- Theory of one-tape linear-time Turing machines
- On functional complexity and superpositions of functions
- A hierarchy based on output multiplicity
- Functions computable with limited access to NP
- Inverting onto functions.
- Some structural properties of SAT
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- Reducing the number of solutions of NP functions
- Competing provers yield improved Karp-Lipton collapse results
- On the complexity of data disjunctions.
- Optimal series-parallel trade-offs for reducing a function to its own graph
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Černý's conjecture and the road colouring problem
- Reductions between disjoint NP-pairs
- Expressive probabilistic description logics
- Graph Isomorphism is in SPP
- On the query complexity of selecting minimal sets for monotone predicates
- Resource bounded immunity and simplicity
- Cluster computing and the power of edge recognition
- Classification and complexity of problems.
- Function operators spanning the arithmetical and the polynomial hierarchy
- Do there exist complete sets for promise classes?
- Solutions to twisted word equations and equations in virtually free groups
- The Shrinking Property for NP and coNP
- Is Valiant-Vazirani's isolation probability improvable?
- scientific article; zbMATH DE number 58287 (Why is no real title available?)
- scientific article; zbMATH DE number 139620 (Why is no real title available?)
- scientific article; zbMATH DE number 1136092 (Why is no real title available?)
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- The consequences of eliminating NP solutions
- Federation and navigation in SPARQL 1.1
- Computable analysis and notions of continuity in \textsc{Coq}
- The isomorphism problem for finite extensions of free groups is in PSPACE
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Classes of computable functions defined by bounds on computation
- Algorithms and Computation
- Average-case intractability vs. worst-case intractability
- Polynomial-time axioms of choice and polynomial-time cardinality
- Foundations of probability-raising causality in Markov decision processes
- The shrinking property for NP and coNP
- Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results
- On the complexity of core, kernel, and bargaining set
- On quasilinear-time complexity theory
- Computing functions with parallel queries to NP
- Complexity classes of equivalence problems revisited
- Symmetric exponential time requires near-maximum circuit size
- The complexity of computing second solutions
- Complexity results for explanations in the structural-model approach
- Probabilistic logic under coherence: complexity and algorithms
- Nondeterministic functions and the existence of optimal proof systems
- Pseudorandom generators against advised context-free languages
This page was built for publication: A taxonomy of complexity classes of functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329166)
