Bounded Query Classes
From MaRDI portal
Publication:3495646
DOI10.1137/0219058zbMath0711.68047OpenAlexW2058277150MaRDI 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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Complexity results for some eigenvector problems, Alternating and empty alternating auxiliary stack automata., A taxonomy of complexity classes of functions, COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA, Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete, A relationship between difference hierarchies and relativized polynomial hierarchies, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Complexity of counting the optimal solutions, Locating \(P\)/poly optimally in the extended low hierarchy, The complexity class θp2: Recent results and applications in AI and modal logic, Query order in the polynomial hierarchy, Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games, Norm-based mechanism design, Weighted Boolean Formula Games, Cluster computing and the power of edge recognition, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison, On parallel hierarchies and \(R_k^i\), The complexity of computing minimal unidirectional covering sets, On the computational cost of disjunctive logic programming: Propositional case, Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting, Generalized possibilistic logic: foundations and applications to qualitative reasoning about uncertainty, On the equivalence of distributed systems with queries and communication, On monotonous oracle machines, Locally definable acceptance types for polynomial time machines, Characterizations of some complexity classes between Θ2p and Δ2p, Promise problems and access to unambiguous computation, Empty alternation, On the power of deterministic reductions to C=P, Updating action domain descriptions, Stability, vertex stability, and unfrozenness for special graph classes, Adaptive logspace reducibility and parallel time, Complexity of Counting the Optimal Solutions, Upper bounds for the complexity of sparse and tally descriptions, \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP], An extension-based approach to belief revision in abstract argumentation, The Complexity Landscape of Outcome Determination in Judgment Aggregation, Relativized logspace and generalized quantifiers over finite ordered structures, ANALYSIS OF QUANTUM FUNCTIONS, Bounded queries to SAT and the Boolean hierarchy, On adaptive DLOGTIME and POLYLOGTIME reductions, A note on P-selective sets and closeness, Computing functions with parallel queries to NP, Complexity of stability, Complexity of Stability., Removing redundancy from a clause, Methods for proving completeness via logical reductions, On the complexity of propositional knowledge base revision, updates, and counterfactuals, Extension and equivalence problems for clause minimal formulae, Complexity-theoretic aspects of expanding cellular automata, Complexity-theoretic aspects of expanding cellular automata, Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy, Function operators spanning the arithmetical and the polynomial hierarchy, Error-bounded probabilistic computations between MA and AM, Reductions to sets of low information content, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, Combining experts' causal judgments, Knowledge-based programs as succinct policies for partially observable domains, On the complexity of the clone membership problem, Exact complexity of exact-four-colorability, Deciding According to the Shortest Computations, Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, Hybrid Elections Broaden Complexity-Theoretic Resistance to Control, Finding Optimal Solutions With Neighborly Help., Relating polynomial time to constant depth, The structure of logarithmic advice complexity classes, Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting, Query Order, The closure of monadic NP, Representing interval orders by weighted bases: some complexity results, Choice logics and their computational properties, COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES, The computational complexity of ideal semantics, Default reasoning from conditional knowledge bases: Complexity and tractable cases, 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, A note on parallel queries and the symmetric-difference hierarchy., A note on unambiguous function classes, Complexity results for explanations in the structural-model approach, The complexity of Kemeny elections
