Computing functions with parallel queries to NP
From MaRDI portal
Publication:673784
DOI10.1016/0304-3975(94)00080-3zbMath0873.68058MaRDI QIDQ673784
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2117/96815
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, On sets bounded truth-table reducible to $P$-selective sets, Monotonous and randomized reductions to sparse sets, ANALYSIS OF QUANTUM FUNCTIONS, Weighted argument systems: basic definitions, algorithms, and complexity results, On adaptive DLOGTIME and POLYLOGTIME reductions, Complexity results for explanations in the structural-model approach, Probabilistic logic under coherence: complexity and algorithms, Complexity of counting the optimal solutions, The computational complexity of ideal semantics, Default reasoning from conditional knowledge bases: Complexity and tractable cases, On the complexity of data disjunctions., Expressive probabilistic description logics, Combining answer set programming with description logics for the semantic web, Graph Isomorphism is in SPP, Complexity of Counting the Optimal Solutions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- NP is as easy as detecting unique solutions
- The complexity of optimization problems
- On counting and approximation
- The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
- Self-witnessing polynomial-time complexity and prime factorization
- Approximation algorithms for combinatorial problems
- A comparison of polynomial time reducibilities
- A note on the graph isomorphism counting problem
- A taxonomy of complexity classes of functions
- Functions computable with nonadaptive queries to NP
- Enumerative counting is hard
- Classes of bounded nondeterminism
- On the Decomposability of $NC$ and $AC$
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- Constant Depth Reducibility
- On the unique satisfiability problem
- Positive Relativizations of Complexity Classes
- Bounded Query Classes
- Relativization of questions about log space computability
- Characterizations of some complexity classes between Θ2p and Δ2p