Bounded Query Classes
From MaRDI portal
Publication:3495646
Recommendations
Cited in
(only showing first 100 items - show all)- Exact complexity of exact-four-colorability
- Representing interval orders by weighted bases: some complexity results
- The computational complexity of ideal semantics
- On bounded query machines
- Bounded query classes and the difference hierarchy
- Bounded queries to SAT and the Boolean hierarchy
- On the complexity of propositional knowledge base revision, updates, and counterfactuals
- Bounding queries in the analytic polynomial-time hierarchy
- 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
- Some connections between bounded query classes and non-uniform complexity.
- The closure of monadic NP
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- A note on unambiguous function classes
- Generalized possibilistic logic: foundations and applications to qualitative reasoning about uncertainty
- An extension-based approach to belief revision in abstract argumentation
- Extension and equivalence problems for clause minimal formulae
- Model checking for fragments of the interval temporal logic HS at the low levels of the polynomial time hierarchy
- 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.
- Restricted information from nonadaptive queries to NP
- On the computational cost of disjunctive logic programming: Propositional case
- Combining experts' causal judgments
- Knowledge-based programs as succinct policies for partially observable domains
- On the complexity of the clone membership problem
- Choice logics and their computational properties
- Complexity of stability
- Complexity-theoretic aspects of expanding cellular automata
- Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- 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
- Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting
- Comparing and aggregating partial orders with Kendall tau distances
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- Function operators spanning the arithmetical and the polynomial hierarchy
- Deciding according to the shortest computations
- 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
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Weighted Boolean formula games
- Complexity of Counting the Optimal Solutions
- scientific article; zbMATH DE number 3930351 (Why is no real title available?)
- scientific article; zbMATH DE number 4060725 (Why is no real title available?)
- On the equivalence of distributed systems with queries and communication
- scientific article; zbMATH DE number 18631 (Why is no real title available?)
- On the power of deterministic reductions to C=P
- Query Order
- Complexity-Restricted Advice Functions
- Adaptive logspace reducibility and parallel time
- Relativized logspace and generalized quantifiers over finite ordered structures
- Complexity results for some eigenvector problems
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- Bounded queries to arbitrary sets
- 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
- The complexity class θp2: Recent results and applications in AI and modal logic
- Query order in the polynomial hierarchy
- Finding Optimal Solutions With Neighborly Help.
- On monotonous oracle machines
- Locally definable acceptance types for polynomial time machines
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
- Promise problems and access to unambiguous computation
- Empty alternation
- The complexity landscape of outcome determination in judgment aggregation
- Reductions to sets of low information content (extended abstract)
- A relationship between difference hierarchies and relativized polynomial hierarchies
- A finite model-theoretical proof of a property of bounded query classes within PH
- THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
- ANALYSIS OF QUANTUM FUNCTIONS
- Complexity of Stability.
- Stability, vertex stability, and unfrozenness for special graph classes
- Complexity-theoretic aspects of expanding cellular automata
- Updating action domain descriptions
- Complexity and scalability of defeasible reasoning with typicality in many-valued weighted knowledge bases
- Finding optimal solutions with neighborly help
- Pinpointing computation with modular queries in the Boolean hierarchy
- A knowledge compilation perspective on queries and transformations for belief tracking
- 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
- Beyond recognizing well-covered graphs
- Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality
- Querying incomplete data: complexity and tractability via Datalog and first-order rewritings
- A rule-based modal framework for causal reasoning
- On adaptive versus nonadaptive bounded query machines
- Complexity results for explanations in the structural-model approach
This page was built for publication: Bounded Query Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495646)
