Boolean constraint satisfaction problems for reaction networks

DOI10.1088/1742-5468/2013/09/P09009MaRDI QIDQ3301686zbMATH OpenFDO

Authors

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.2480

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Population dynamics (general) (92D25) Combinatorial probability (60C05) Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics (82C31)

Abstract: We define and study a class of (random) Boolean constraint satisfaction problems representing minimal feasibility constraints for networks of chemical reactions. The constraints we consider encode, respectively, for hard mass-balance conditions (where the consumption and production fluxes of each chemical species are matched) and for soft mass-balance conditions (where a net production of compounds is in principle allowed). We solve these constraint satisfaction problems under the Bethe approximation and derive the corresponding Belief Propagation equations, that involve 8 different messages. The statistical properties of ensembles of random problems are studied via the population dynamics methods. By varying a chemical potential attached to the activity of reactions, we find first order transitions and strong hysteresis, suggesting a non-trivial structure in the space of feasible solutions.

Recommendations

• Analyzing Pathways Using SAT-Based Approaches
• scientific article; zbMATH DE number 7301529
• Threshold properties of random Boolean constraint satisfaction problems
• On the complexity of reconstructing chemical reaction networks
• On the freezing of variables in random constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 412153 (Why is no real title available?)
• scientific article; zbMATH DE number 1090658 (Why is no real title available?)
• Chemical biophysics. Quantitative analysis of cellular systems.
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Propagation of external regulation and asynchronous dynamics in random Boolean networks
• The cavity method at zero temperature
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Typical properties of optimal growth in the von Neumann expanding model for large random economies
• Von Neumann's expanding model on random graphs

Cited in

(1)

• scientific article; zbMATH DE number 7070937 (Why is no real title available?)

This page was built for publication: Boolean constraint satisfaction problems for reaction networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301686)