Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very large instances. Moreover, it is still unclear what are the key features that make a discrete combinatorial optimization problem hard to solve. Here we study random K-satisfiability problems with K=3,4, which are known to be very hard close to the SAT-UNSAT threshold, where problems stop having solutions. We show that the backtracking survey propagation algorithm, in a time practically linear in the problem size, is able to find solutions very close to the threshold, in a region unreachable by any other algorithm. All solutions found have no frozen variables, thus supporting the conjecture that only unfrozen solutions can be found in linear time, and that a problem becomes impossible to solve in linear time when all solutions contain frozen variables.
We analyze the translational and rotational motion of an ellipsoidal Brownian particle from the viewpoint of stochastic thermodynamics. The particle's Brownian motion is driven by external forces and torques and takes place in an heterogeneous thermal environment where friction coefficients and (local) temperature depend on space and time. Our analysis of the particle's stochastic thermodynamics is based on the entropy production associated with single particle trajectories. It is motivated by the recent discovery that the overdamped limit of vanishing inertia effects (as compared to viscous fricion) produces a so-called “anomalous” contribution to the entropy production, which has no counterpart in the overdamped approximation, when inertia effects are simply discarded. Here we show that rotational Brownian motion in the overdamped limit generates an additional contribution to the “anomalous” entropy. We calculate its specific form by performing a systematic singular perturbation analysis for the generating function of the entropy production. As a side result, we also obtain the (well-known) equations of motion in the overdamped limit. We furthermore investigate the effects of particle shape and give explicit expressions of the “anomalous entropy” for prolate and oblate spheroids and for near-spherical Brownian particles.
4 October 2023 in Physica A: Statistical Mechanics and its Applications
Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algorithm for computing approximate solutions in Θ(N) for the maximum exact 3-satisfiability (MAX-E-3-SAT) problem by using supervised learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random conjunctive normal form instances of the MAX-E-3-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art maximum satisfiability solvers, it can solve substantially larger and more complicated problems than it ever saw during training.