Computing functions with parallel queries to NP

DOI10.1016/0304-3975(94)00080-3zbMath0873.68058OpenAlexW2072808963MaRDI 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

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (21)

Probabilistic logic under coherence: complexity and algorithms ⋮ UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ Resource-bounded kolmogorov complexity revisited ⋮ Sparse sets, approximable sets, and parallel queries to NP ⋮ Complexity of counting the optimal solutions ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Expressive probabilistic description logics ⋮ Combining answer set programming with description logics for the semantic web ⋮ Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP ⋮ Complexity of Counting the Optimal Solutions ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Weighted argument systems: basic definitions, algorithms, and complexity results ⋮ Graph Isomorphism is in SPP ⋮ Combining experts' causal judgments ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ The computational complexity of ideal semantics ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ On the complexity of data disjunctions. ⋮ Complexity results for explanations in the structural-model approach

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

This page was built for publication: Computing functions with parallel queries to NP