Theory-Contraction is NP-Complete

DOI10.1093/JIGPAL/11.6.675MaRDI QIDQ4465167zbMATH OpenOpenAlexFDO

Authors Neil Tennant

Publication date 27 May 2004

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/8e62c905f6044495a2a04b59afde809495dfde4a

zbMATH Keywords

computational complexitycontractions of dependency-networksfinite belief-systems

Mathematics Subject Classification ID

Logics of knowledge and belief (including belief change) (03B42) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Edge-contraction problems
• Contractibility and NP-completeness
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Node-and edge-deletion NP-complete problems
• A simple variant of node connectivity is NP-complete

Cited in

(4)

• Preference-based belief revision for rule-based agents
• New foundations for a relational theory of theory-revision
• Belief-revision, the Ramsey test, monotonicity, and the so-called impossibility results
• Contracting intuitionistic theories

This page was built for publication: Theory-Contraction is NP-Complete

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