Simplifying Random Satisfiability Problem by Removing Frustrating Interactions

Details Simplifying Random Satisfiability Problem by Removing Frustrating Interactions Simplifying Random Satisfiability Problem by Removing Frustrating Interactions

2006-06-06

arxiv.org/abs/cond-mat/0606128v1

Physics

Condensed Matter

Statistical Mechanics

21 pages, 16 figures

Scientific paper

10.1103/PhysRevE.74.041105

How can we remove some interactions in a constraint satisfaction problem (CSP) such that it still remains satisfiable? In this paper we study a modified survey propagation algorithm that enables us to address this question for a prototypical CSP, i.e. random K-satisfiability problem. The average number of removed interactions is controlled by a tuning parameter in the algorithm. If the original problem is satisfiable then we are able to construct satisfiable subproblems ranging from the original one to a minimal one with minimum possible number of interactions. The minimal satisfiable subproblems will provide directly the solutions of the original problem.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-2892