اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA review of the Statistical Mechanics approach to Random Optimization Problems
33
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We review the connection between statistical mechanics and the analysis of random optimization problems, with particular emphasis on the random k-SAT problem. We discuss and characterize the different phase transitions that are met in these problems, starting from basic concepts. We also discuss how statistical mechanics methods can be used to investigate the behavior of local search and decimation based algorithms.
قيم البحث
اقرأ أيضاً
The basic notions of statistical mechanics (microstates, multiplicities) are quite simple, but understanding how the second law arises from these ideas requires working with cumbersomely large numbers. To avoid getting bogged down in mathematics, one
can compute multiplicities numerically for a simple model system such as an Einstein solid -- a collection of identical quantum harmonic oscillators. A computer spreadsheet program or comparable software can compute the required combinatoric functions for systems containing a few hundred oscillators and units of energy. When two such systems can exchange energy, one immediately sees that some configurations are overwhelmingly more probable than others. Graphs of entropy vs. energy for the two systems can be used to motivate the theoretical definition of temperature, $T= (partial S/partial U)^{-1}$, thus bridging the gap between the classical and statistical approaches to entropy. Further spreadsheet exercises can be used to compute the heat capacity of an Einstein solid, study the Boltzmann distribution, and explore the properties of a two-state paramagnetic system.
Transient chaos is an ubiquitous phenomenon characterizing the dynamics of phase space trajectories evolving towards a steady state attractor in physical systems as diverse as fluids, chemical reactions and condensed matter systems. Here we show that
transient chaos also appears in the dynamics of certain efficient algorithms searching for solutions of constraint satisfaction problems that include scheduling, circuit design, routing, database problems or even Sudoku. In particular, we present a study of the emergence of hardness in Boolean satisfiability ($k$-SAT), a canonical class of constraint satisfaction problems, by using an analog deterministic algorithm based on a system of ordinary differential equations. Problem hardness is defined through the escape rate $kappa$, an invariant measure of transient chaos of the dynamical system corresponding to the analog algorithm, and it expresses the rate at which the trajectory approaches a solution.We show that for a given density of constraints and fixed number of Boolean variables $N$, the hardness of formulas in random $k$-SAT ensembles has a wide variation, approximable by a lognormal distribution. We also show that when increasing the density of constraints $alpha$, hardness appears through a second-order phase transition at $alpha_{chi}$ in the random 3-SAT ensemble where dynamical trajectories become transiently chaotic. A similar behavior is found in 4-SAT as well, however, such transition does not occur for 2-SAT. This behavior also implies a novel type of transient chaos in which the escape rate has an exponential-algebraic dependence on the critical parameter $kappa sim N^{B|alpha - alpha_{chi}|^{1-gamma}}$ with $0< gamma < 1$. We demonstrate that the transition is generated by the appearance of metastable basins in the solution space as the density of constraints $alpha$ is increased.
Since the very early days of quantum theory there have been numerous attempts to interpret quantum mechanics as a statistical theory. This is equivalent to describing quantum states and ensembles together with their dynamics entirely in terms of phas
e-space distributions. Finite dimensional systems have historically been an issue. In recent works [Phys. Rev. Lett. 117, 180401 and Phys. Rev. A 96, 022117] we presented a framework for representing any quantum state as a complete continuous Wigner function. Here we extend this work to its partner function -- the Weyl function. In doing so we complete the phase-space formulation of quantum mechanics -- extending work by Wigner, Weyl, Moyal, and others to any quantum system. This work is structured in three parts. Firstly we provide a brief modernized discussion of the general framework of phase-space quantum mechanics. We extend previous work and show how this leads to a framework that can describe any system in phase space -- putting it for the first time on a truly equal footing to Schrodingers and Heisenbergs formulation of quantum mechanics. Importantly, we do this in a way that respects the unifying principles of parity and displacement in a natural broadening of previously developed phase space concepts and methods. Secondly we consider how this framework is realized for different quantum systems; in particular we consider the proper construction of Weyl functions for some example finite dimensional systems. Finally we relate the Wigner and Weyl distributions to statistical properties of any quantum system or set of systems.
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the
problem to decide for a vertex set $U subseteq V$, if there exists a textit{minimal} dominating set $S$ with $Usubseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.
We propose a lattice model for RNA based on a self-interacting two-tolerant trail. Self-avoidance and elements of tertiary structure are taken into account. We investigate a simple version of the model in which the native state of RNA consists of jus
t one hairpin. Using exact arguments and Monte Carlo simulations we determine the phase diagram for this case. We show that the denaturation transition is first order and can either occur directly or through an intermediate molten phase.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
