Preprocessing of intractable problems

DOI10.1006/INCO.2001.3043zbMATH Open1012.68082OpenAlexW2085393535MaRDI QIDQ1854544FDOQ1854544

Authors: Marco Cadoli, F. M. Donini, Paolo Liberatore, Marco Schaerf 

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2001.3043

Recommendations

• Monotonic reductions, representative equivalence, and compilation of intractable problems
• Recent Developments in the Theory of Pre-processing
• Compilability of propositional abduction
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• Lower bounds for kernelizations and other preprocessing procedures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Knowledge representation (68T30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A theory of diagnosis from first principles
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Knowledge compilation and theory approximation
• Title not available (Why is that?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Title not available (Why is that?)
• The polynomial-time hierarchy
• Title not available (Why is that?)
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• An algorithm to compute circumscription
• The complexity of model checking for circumscriptive formulae
• Some consequences of non-uniform conditions on uniform classes
• Circumscription - a form of non-monotonic reasoning
• Title not available (Why is that?)
• The size of a revised knowledge base
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Preprocessing of intractable problems
• Amortized Computational Complexity
• Computing circumscriptive databases
• On compact representations of propositional circumscription
• Is intractability of nonmonotonic reasoning a real drawback?
• Reducing belief revision to circumscription (and vice versa)
• Default reasoning using classical logic
• Title not available (Why is that?)
• Off-line reasoning for on-line efficiency: knowledge bases
• Implicates and prime implicates in random 3-SAT

Cited In (17)

• Preprocessing complementarity problems
• Preprocessing under uncertainty
• Parameter compilation
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• A parametric analysis of the state-explosion problem in model checking
• What makes propositional abduction tractable
• On the complexity of case-based planning
• On the complexity of second-best abductive explanations
• On the complexity of existential positive queries
• Sublinear-time reductions for big data computing
• Preprocessing for DQBF
• Knowledge compilation with empowerment
• Preprocessing of intractable problems
• Common equivalence and size of forgetting from Horn formulae
• Semantic forgetting in answer set programming
• Compiling propositional weighted bases

This page was built for publication: Preprocessing of intractable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854544)