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 (85)
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
This page was built for publication: Bounded Query Classes