Theory-Contraction is NP-Complete
From MaRDI portal
Publication:4465167
DOI10.1093/jigpal/11.6.675zbMath1042.03018MaRDI QIDQ4465167
Publication date: 27 May 2004
Published in: Logic Journal of IGPL (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/8e62c905f6044495a2a04b59afde809495dfde4a
03B42: Logics of knowledge and belief (including belief change)
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Contracting intuitionistic theories, 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