Fault Tolerant Boolean Satisfiability

Details Fault Tolerant Boolean Satisfiability Fault Tolerant Boolean Satisfiability

2011-09-28

arxiv.org/abs/1109.6348v1

Journal Of Artificial Intelligence Research, Volume 25, pages 503-527, 2006

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1914

A delta-model is a satisfying assignment of a Boolean formula for which any small alteration, such as a single bit flip, can be repaired by flips to some small number of other bits, yielding a new satisfying assignment. These satisfying assignments represent robust solutions to optimization problems (e.g., scheduling) where it is possible to recover from unforeseen events (e.g., a resource becoming unavailable). The concept of delta-models was introduced by Ginsberg, Parkes and Roy (AAAI 1998), where it was proved that finding delta-models for general Boolean formulas is NP-complete. In this paper, we extend that result by studying the complexity of finding delta-models for classes of Boolean formulas which are known to have polynomial time satisfiability solvers. In particular, we examine 2-SAT, Horn-SAT, Affine-SAT, dual-Horn-SAT, 0-valid and 1-valid SAT. We see a wide variation in the complexity of finding delta-models, e.g., while 2-SAT and Affine-SAT have polynomial time tests for delta-models, testing whether a Horn-SAT formula has one is NP-complete.

Affiliated with

Also associated with

No associations

Rating

Fault Tolerant Boolean Satisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fault Tolerant Boolean Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault Tolerant Boolean Satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-150778