Preprocessing of intractable problems

DOI10.1006/INCO.2001.3043MaRDI QIDQ1854544zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(17)

• Preprocessing complementarity problems
• Preprocessing under uncertainty
• Parameter compilation
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• A parametric analysis of the state-explosion problem in model checking
• What makes propositional abduction tractable
• On the complexity of second-best abductive explanations
• On the complexity of case-based planning
• 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)