Bounded Query Classes

From MaRDI portal
Revision as of 22:43, 4 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:3495646

DOI10.1137/0219058zbMath0711.68047OpenAlexW2058277150MaRDI QIDQ3495646

Klaus W. Wagner

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




Related Items (85)

Complexity results for some eigenvector problemsAlternating and empty alternating auxiliary stack automata.A taxonomy of complexity classes of functionsCOMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRAPropositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-completeA relationship between difference hierarchies and relativized polynomial hierarchiesRecognizing when greed can approximate maximum independent sets is complete for parallel access to NPGuarantees for the success frequency of an algorithm for finding Dodgson-election winnersComplexity of counting the optimal solutionsLocating \(P\)/poly optimally in the extended low hierarchyThe complexity class θp2: Recent results and applications in AI and modal logicQuery order in the polynomial hierarchyToward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic gamesNorm-based mechanism designWeighted Boolean Formula GamesCluster computing and the power of edge recognitionExact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NPA novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparisonOn parallel hierarchies and \(R_k^i\)The complexity of computing minimal unidirectional covering setsOn the computational cost of disjunctive logic programming: Propositional caseComplexity results for preference aggregation over \((m)\)CP-nets: max and rank votingGeneralized possibilistic logic: foundations and applications to qualitative reasoning about uncertaintyOn the equivalence of distributed systems with queries and communicationOn monotonous oracle machinesLocally definable acceptance types for polynomial time machinesCharacterizations of some complexity classes between Θ2p and Δ2pPromise problems and access to unambiguous computationEmpty alternationOn the power of deterministic reductions to C=PUpdating action domain descriptionsStability, vertex stability, and unfrozenness for special graph classesAdaptive logspace reducibility and parallel timeComplexity of Counting the Optimal SolutionsUpper 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 argumentationThe Complexity Landscape of Outcome Determination in Judgment AggregationRelativized logspace and generalized quantifiers over finite ordered structuresANALYSIS OF QUANTUM FUNCTIONSBounded queries to SAT and the Boolean hierarchyOn adaptive DLOGTIME and POLYLOGTIME reductionsA note on P-selective sets and closenessComputing functions with parallel queries to NPComplexity of stabilityComplexity of Stability.Removing redundancy from a clauseMethods for proving completeness via logical reductionsOn the complexity of propositional knowledge base revision, updates, and counterfactualsExtension and equivalence problems for clause minimal formulaeComplexity-theoretic aspects of expanding cellular automataComplexity-theoretic aspects of expanding cellular automataModel checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchyFunction operators spanning the arithmetical and the polynomial hierarchyError-bounded probabilistic computations between MA and AMReductions to sets of low information contentRecognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NPTHE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELSCombining experts' causal judgmentsKnowledge-based programs as succinct policies for partially observable domainsOn the complexity of the clone membership problemExact complexity of exact-four-colorabilityDeciding According to the Shortest ComputationsComplexity classes between $\Theta _k^P$ and $\Delta _k^P$Hybrid Elections Broaden Complexity-Theoretic Resistance to ControlFinding Optimal Solutions With Neighborly Help.Relating polynomial time to constant depthThe structure of logarithmic advice complexity classesComplexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority votingQuery OrderThe closure of monadic NPRepresenting interval orders by weighted bases: some complexity resultsChoice logics and their computational propertiesCOMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCESThe computational complexity of ideal semanticsDefault reasoning from conditional knowledge bases: Complexity and tractable casesOn the complexity of data disjunctions.Propositional default logics made easier: computational complexity of model checking.Commutative queriesBounded queries, approximations, and the Boolean hierarchyOptimal series-parallel trade-offs for reducing a function to its own graphA note on parallel queries and the symmetric-difference hierarchy.A note on unambiguous function classesComplexity results for explanations in the structural-model approachThe complexity of Kemeny elections







This page was built for publication: Bounded Query Classes