Computing functions with parallel queries to NP

DOI10.1016/0304-3975(94)00080-3zbMath0873.68058MaRDI QIDQ673784

Birgit Jenner, Jacobo Toran

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

Mathematics Subject Classification ID

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, 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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item