Biomedical subjects

S Moghimi-Araghi

Publications and source records attributed to S Moghimi-Araghi.

2 recordsLinked to original sources

PubMed2006

Simplifying random satisfiability problems by removing frustrating interactions.

How can we remove some interactions (generate shorter clauses) 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 directly provide the solutions of the original problem.

Journal Article↗

PubMed2005

Biased random satisfiability problems: from easy to hard instances.

In this paper we study biased random K -satisfiability ( K -SAT) problems in which each logical variable is negated with probability p . This generalization provides us a crossover from easy to hard problems and would help us in a better understanding of the typical complexity of random K -SAT problems. The exact solution of 1-SAT case is given. The critical point of K -SAT problems and results of replica method are derived in the replica symmetry framework. It is found that in this approximation alpha(c) proportional p(-(K-1)) for p --> 0. Solving numerically the survey propagation equations for K = 3 we find that for p < p* approximately 0.17 there is no replica symmetry breaking and still the SAT-UNSAT transition is discontinuous.

Journal Article↗