Applying Max-2SAT to Efficient Belief Revision

Belief revision is a NP-hard problem even when the Knowledge Base (Σ) is formed by Horn clauses. In this paper, we present a new belief revision operator running efficiently if the initial knowledge base is a two conjunctive form(conjunction of unit or binary clauses, denoted as 2-CF).Such revision operator *_I on a new formula F, denoted as (Σ *_IF), relies heavily on the selected model I of F. If the model Ican be computed in polynomial time (e.g. if F is Horn or a 2-CF), then the complete belief revision process has a polynomial time complexity. However, if F has not restrictions, our proposal request to apply only one NP oracle call (that is, the necessary call to compute a model of F) that involves an exponential time over the length of F. Afterwards, to compute (Σ *_I F) is done in a polynomial time over the length of Σ. It is common to consider the length of Σ much longer than the length of F. Thus, our proposal of belief revision is in the complexity class PNP[1].