Preprocessing of intractable problems

DOI10.1006/inco.2001.3043zbMath1012.68082OpenAlexW2085393535MaRDI QIDQ1854544

Marco Schaerf, Marco Cadoli, Francesco M. Donini, Paolo Liberatore

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

Mathematics Subject Classification ID

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

Related Items

Knowledge Compilation with Empowerment ⋮ What makes propositional abduction tractable ⋮ Semantic forgetting in answer set programming ⋮ On the complexity of second-best abductive explanations ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ On the complexity of case-based planning ⋮ On the complexity of existential positive queries ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Sublinear-time reductions for big data computing ⋮ Preprocessing of intractable problems ⋮ Compiling propositional weighted bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Some consequences of non-uniform conditions on uniform classes
• A theory of diagnosis from first principles
• An algorithm to compute circumscription
• Circumscription - a form of non-monotonic reasoning
• The complexity of model checking for circumscriptive formulae
• The polynomial-time hierarchy
• 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)
• Preprocessing of intractable problems
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• The size of a revised knowledge base
• Off-line reasoning for on-line efficiency: knowledge bases
• Default reasoning using classical logic
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Implicates and prime implicates in random 3-SAT
• Amortized Computational Complexity
• Knowledge compilation and theory approximation
• Fixed-Parameter Tractability and Completeness I: Basic Results