On the hardness of approximate reasoning

DOI10.1016/0004-3702(94)00092-1zbMath1506.68143OpenAlexW1964821516MaRDI QIDQ2674206

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(94)00092-1

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items

On preprocessing techniques and their impact on propositional model counting, An enumerative algorithm for \#2SAT, Computing the fault tolerance of multi-agent deployment, An extended depth-first search algorithm for optimal triangulation of Bayesian networks, Approximate algorithms for credal networks with binary variables, Model counting for CNF formulas of bounded modular treewidth, Phase transitions of PP-complete satisfiability problems, On probabilistic inference by weighted model counting, Expressive probabilistic description logics, Understanding the role of noise in stochastic local search: analysis and experiments, Computing and estimating the volume of the solution space of SMT(LA) constraints, Algorithms for four variants of the exact satisfiability problem, Towards a dichotomy theorem for the counting constraint satisfaction problem, The effect of combination functions on the complexity of relational Bayesian networks, Defaults and relevance in model-based reasoning, Exact stochastic constraint optimisation with applications in network analysis, Algorithms for Propositional Model Counting, Reasoning with models, Hybrid Helmholtz machines: a gate-based quantum circuit implementation, Propagation effects of model-calculated probability values in Bayesian networks, Exploiting Database Management Systems and Treewidth for Counting, Solving projected model counting by utilizing treewidth and its limits, Fast local search methods for solving limited memory influence diagrams, Permissive planning: Extending classical planning to uncertain task domains., IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?, An intercausal cancellation model for Bayesian-network engineering, Semantics and complexity of abduction from default theories, Approximating the least hypervolume contributor: NP-hard in general, but fast in practice, Are hitting formulas hard for resolution?, Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial, On Imperfect Recall in Multi-Agent Influence Diagrams, Picturing Counting Reductions with the ZH-Calculus, Unnamed Item, Tractable inference in credal sentential decision diagrams, Thirty years of credal networks: specification, algorithms and complexity, The complexity of Bayesian networks specified by propositional and relational languages, A structured view on weighted counting with relations to counting, quantum computation and applications, The consequences of eliminating NP solutions, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Disjunctive closures for knowledge compilation, Robustifying sum-product networks, Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting, \(P\)-top-\(k\) queries in a probabilistic framework from information extraction models, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, Some thoughts on knowledge-enhanced machine learning, New width parameters for SAT and \#SAT, Tree decompositions with small cost, Algorithms for propositional model counting, Approximating the volume of unions and intersections of high-dimensional geometric objects, Optimal control in dynamic food supply chains using big data, Understanding the scalability of Bayesian network inference using clique tree growth curves, The number of independent sets in a connected graph and its complement, A probabilistic approach to solving crossword puzzles, Probabilistic sentence satisfiability: an approach to PSAT, Using binary patterns for counting falsifying assignments of conjunctive forms, Definability for model counting, On hard instances of non-commutative permanent, Faster graph coloring in polynomial space, The number of independent sets in unicyclic graphs with a given diameter, Unnamed Item, Approximate weighted model integration on DNF structures, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, Unnamed Item, The number of independent sets in unicyclic graphs, Complexity results for structure-based causality., Expected computations on color spanning sets, Evaluation of Bayesian networks with flexible state-space abstraction methods, Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks, Complexity results for explanations in the structural-model approach

Cites Work