Bounded Query Classes
From MaRDI portal
Publication:3495646
DOI10.1137/0219058zbMath0711.68047MaRDI QIDQ3495646
Publication date: 1990
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0219058
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Adaptive logspace reducibility and parallel time, Relativized logspace and generalized quantifiers over finite ordered structures, Complexity results for some eigenvector problems, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA, Upper bounds for the complexity of sparse and tally descriptions, A relationship between difference hierarchies and relativized polynomial hierarchies, THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, ANALYSIS OF QUANTUM FUNCTIONS, On adaptive DLOGTIME and POLYLOGTIME reductions, A note on P-selective sets and closeness, Computing functions with parallel queries to NP, Removing redundancy from a clause, Methods for proving completeness via logical reductions, Complexity results for explanations in the structural-model approach, The complexity of Kemeny elections, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Complexity of counting the optimal solutions, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], Exact complexity of exact-four-colorability, Representing interval orders by weighted bases: some complexity results, The computational complexity of ideal semantics, Bounded queries to SAT and the Boolean hierarchy, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Relating polynomial time to constant depth, The structure of logarithmic advice complexity classes, A taxonomy of complexity classes of functions, Locating \(P\)/poly optimally in the extended low hierarchy, On parallel hierarchies and \(R_k^i\), The closure of monadic NP, Default reasoning from conditional knowledge bases: Complexity and tractable cases, A note on unambiguous function classes, Extension and equivalence problems for clause minimal formulae, On the complexity of data disjunctions., Propositional default logics made easier: computational complexity of model checking., Commutative queries, Bounded queries, approximations, and the Boolean hierarchy, Optimal series-parallel trade-offs for reducing a function to its own graph, Alternating and empty alternating auxiliary stack automata., On the computational cost of disjunctive logic programming: Propositional case, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, Error-bounded probabilistic computations between MA and AM, A note on parallel queries and the symmetric-difference hierarchy., Cluster computing and the power of edge recognition, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, Hybrid Elections Broaden Complexity-Theoretic Resistance to Control, Complexity of Counting the Optimal Solutions, On the power of deterministic reductions to C=P, Query Order
