Adversarial Satisfiability Problem

Details Adversarial Satisfiability Problem Adversarial Satisfiability Problem

2010-11-04

arxiv.org/abs/1011.1273v1

J. Stat. Mech. (2011) P03023

Computer Science

Computational Complexity

Scientific paper

10.1088/1742-5468/2011/03/P03023

We study the adversarial satisfiability problem, where the adversary can choose whether variables are negated in clauses or not in order to make the resulting formula unsatisfiable. This is one case of a general class of adversarial optimization problems that often arise in practice and are algorithmically much harder than the standard optimization problems. We use the cavity method to compute large deviations of the entropy in the random satisfiability problem with respect to the negation-configurations. We conclude that in the thermodynamic limit the best strategy the adversary can adopt is extremely close to simply balancing the number of times every variable is and is not negated. We also conduct a numerical study of the problem, and find that there are very strong pre-asymptotic effects that are due to the fact that for small sizes exponential and factorial growth is hardly distinguishable.

Affiliated with

Also associated with

No associations

Rating

Adversarial Satisfiability Problem 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 Adversarial Satisfiability Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adversarial Satisfiability Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453069