Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms

The computational complexity of solving random 3-Satisfiability (3-SAT) problems is investigated using statistical physics concepts and techniques related to phase transitions, growth processes and (real-space) renormalization flows. 3-SAT is a representative example of hard computational tasks; it consists in knowing whether a set of αN randomly drawn logical constraints involving N Boolean variables can be satisfied altogether or not. Widely used solving procedures, as the Davis-Putnam-Loveland-Logemann (DPLL) algorithm, perform a systematic search for a solution, through a sequence of trials and errors represented by a search tree. The size of the search tree accounts for the computational complexity, i.e. the amount of computational efforts, required to achieve resolution. In the present study, we identify, using theory and numerical experiments, easy (size of the search tree scaling polynomially with N) and hard (exponential scaling) regimes as a function of the ratio α of constraints per variable. The typical complexity is explicitly calculated in the different regimes, in very good agreement with numerical simulations. Our theoretical approach is based on the analysis of the growth of the branches in the search tree under the operation of DPLL. On each branch, the initial 3-SAT problem is dynamically turned into a more generic 2+p-SAT problem, where p and 1 - p are the fractions of constraints involving three and two variables respectively. The growth of each branch is monitored by the dynamical evolution of α and p and is represented by a trajectory in the static phase diagram of the random 2+p-SAT problem. Depending on whether or not the trajectories cross the boundary between satisfiable and unsatisfiable phases, single branches or full trees are generated by DPLL, resulting in easy or hard resolutions. Our picture for the origin of complexity can be applied to other computational problems solved by branch and bound algorithms. Received 10 March 2001     

Exact Analytical Solution of the Schrödinger Equation for an N-Identical Body-Force System

A mathematical method is presented for solving the Schr?dinger equation for a system of identical body forces. The N-body forces are more easily introduced and treated within the hyperspherical harmonics. The problem of the N-body potential has been used at the level of both classical and quantum mechanics. The hypercentral interacting potential is assumed to depend on the hyperradius x = (ξ₁² + ξ₂² + ⋯ + ξ_N−1²)^1/2 only, where ξ₁,ξ₂,…,ξ_N−1 are Jacobi relative coordinates which are functions of N-particle relative positions r₁₂,r₂₃,…,r_N1. The problem of the harmonic oscillator and the Coulomb-type potential has been widely studied in different contexts. Using the N-body potential V(x) = ax² + bx − (c/x) as an example, and assuming an ansatz for the eigenfunction, an exact analytical solution of the Schr?dinger equation for an N-body system in three dimensions is obtained. This method is also applicable to some other types of potentials for N-identical interacting particles.     

Evolution of a Model Quantum System¶ Under Time Periodic Forcing:¶Conditions for Complete Ionization

We analyze the time evolution of a one-dimensional quantum system with an attractive delta function potential whose strength is subjected to a time periodic (zero mean) parametric variation η(t). We show that for generic η(t), which includes the sum of any finite number of harmonics, the system, started in a bound state will get fully ionized as t→∞. This is irrespective of the magnitude or frequency (resonant or not) of η(t). There are however exceptional, very non-generic η(t), that do not lead to full ionization, which include rather simple explicit periodic functions. For these η(t) the system evolves to a nontrivial localized stationary state which is related to eigenfunctions of the Floquet operator. Received: 1 November 2000 / Accepted: 5 February 2001     

On the Large-Distance Behavior of Correlations for a Hierarchical N-Component Classical Vector Model in Three Dimensions

We consider the correlation functions for a hierarchical N-component classical vector model in three dimensions. For N = , we find explicitly the eigenvalues and global eigenfunctions of the linearized renormalization group transformation. In a very direct way, this yields the correlation functions for the N = model. In particular, we check that the two-point function has canonical decay.     

Anomalous light-induced drift of lithium atoms in a mixture of noble gases

This paper is a theoretical study of the spectral features of the velocity of light-induced drift (LID) of lithium atoms (⁷Li and ⁶Li) in a binary mixture of noble gases: Ne + Ar, Ne + Kr, and Ne + Xe. The spectral shape of the LID signal is predicted to depend strongly on the fraction ξ of neon in the buffer mixture in the range ξ≈0.8–0.9 (ξ=N _Ne/N _b, where N _Ne is the neon concentration, and N _b is the total concentration of the buffer particles). When the velocity of anomalous LID is treated as a function of the radiation frequency, it is found to have one, three, five, or seven zeros and to differ substantially from the dispersion-curve-like behavior with one zero predicted by the standard LID theory with velocity-independent transport collision rates. The reason for these additional zeros of the drift velocity is the alternating-sign dependence on the lithium-atom velocity of the relative difference of transport rates of collisions between buffer particles and excited and unexcited atoms. What is also established is that the anomalous LID of lithium atoms can be observed at almost all temperatures, depending on the value of ξ. At a fixed temperature, anomalous LID can be observed only in a narrow range of values of the fraction of neon in the buffer mixture, Δξ≈0.02. The results make possible highly precise testing in the LID experiments of the interatomic potentials used in calculations of the velocity spectrum of anomalous LID. Zh. éksp. Teor. Fiz. 116, 1587–1600 (November 1999)     

Renormalization Group Flow¶of the Two-Dimensional Hierarchical Coulomb Gas

We consider a quasilinear parabolic differential equation associated with the renormalization group transformation of the two-dimensional hierarchical Coulomb system in the limit as the size of the block L&\darr; 1. We show that the initial value problem is well defined in a suitable function space and the solution converges, as t→∞, to one of the countably infinite equilibrium solutions. The j ^th nontrivial equilibrium solution bifurcates from the trivial one at . These solutions are fully described and we provide a complete analysis of their local and global stability for all values of inverse temperature β >0. Gallavotti and Nicoló's conjecture on infinite sequence of “phases transitions” is also addressed. Our results rule out an intermediate phase between the plasma and the Kosterlitz–Thouless phases, at least in the hierarchical model we consider. Received: 29 November 1999 / Accepted: 13 January 2001     

Renormalization group functions of the φ<Superscript>4</Superscript> theory from high-temperature expansions

It has been previously shown that calculation of the renormalization group (RG) functions of scalar ϕ⁴ theory reduces to analysis of thermodynamic properties of the Ising model. Using high-temperature expansions for the latter, RG functions of the four-dimensional theory can be calculated for arbitrary coupling constant g with an accuracy of 10⁻⁴ for the Gell-Mann-Low function β(g) and with an accuracy of 10⁻³–10⁻² for anomalous dimensions. The expansions of the renormalization group functions up to the 13th order in g ^−1/2 have been obtained.     

Hierarchical Spherical Model from a Geometric Point of View

A continuous version of the hierarchical spherical model at dimension d=4 is investigated. Two limit distributions of the block spin variable X ^γ , normalized with exponents γ=d+2 and γ=d at and above the critical temperature, are established. These results are proven by solving certain evolution equations corresponding to the renormalization group (RG) transformation of the O(N) hierarchical spin model of block size L ^d in the limit L ↓1 and N→∞. Starting far away from the stationary Gaussian fixed point the trajectories of these dynamical system pass through two different regimes with distinguishable crossover behavior. An interpretation of this trajectories is given by the geometric theory of functions which describe precisely the motion of the Lee–Yang zeroes. The large-N limit of RG transformation with L ^d fixed equal to 2, at the criticality, has recently been investigated in both weak and strong (coupling) regimes by Watanabe (J. Stat. Phys. 115:1669–1713, 2004) . Although our analysis deals only with N=∞ case, it complements various aspects of that work. D.H.U. Marchetti partially supported by CNPq and FAPESP. W.R.P. Conti supported by FAPESP under grant 05/57416-8.     

Convergence and gauge dependence properties of the resummed one-loop quark-quark scattering amplitude in perturbative QCD

The one-loop QCD effective charge α _s ^eff for quark-quark scattering is derived by diagrammatic resummation of the one-loop amplitude using an arbitrary covariant gauge. Except for the particular choice of gauge parameter ξ = −3, α _s ^eff is found to increase with increasing physical scale, Q, as lnQ or ln² Q. For ξ = −3, α _s ^eff decreases with increasing Q and satisfies a renormalization group equation. Also, except for the case ξ = 19/9, convergence radii of geometric series are found to impose upper limits on Q. The text was submitted by the author in English.     

On the theoretical relationship between the Monin-Obukhov stability parameter and the bulk Richardson number

Summary Nomograms were constructed to determine relations among different stability parameters in the surface layer. The variables interrelated were the Monin-Obukhov stability parameter, ξ=z/L, the bulk Richardson number, Ri_b, and the PasquillA-F stability classes. Also, the nomograms were used to estimate the Monin-Obukhov length variation, with respect to changes in surface roughness and atmospheric stability.     

On spectral asymptotics for domains with fractal boundaries

We discuss the spectral properties of the Laplacian for domains Ω with fractal boundaries. The main goal of the article is to find the second term of spectral asymptotics of the counting functionN(λ) or its integral transformations: Θ-function, ξ-function. For domains with smooth boundaries the order of the second term ofN(λ) (under “billiard condition”) is one half of the dimension of the boundary. In the case of fractal boundaries the well-known Weyl-Berry hypothesis identifies it with one half of the Hausdorff dimension of ∂Ω, and the modified Weyl-Berry conjecture with one half of the Minkowski dimension of ∂Ω. We find the spectral asymptotics for three natural broad classes of fractal boundaries (cabbage type, bubble type and web type) and show that the Minkowski dimension gives the proper answer for cabbage type of boundaries (due to “one dimensional structure” of the cabbage type fractals), but the answers are principally different in the two other cases.     

Two-variable Hermite Polynomial State and Its Wigner Function

In this paper we obtain the Wigner functions of two-variable Hermite polynomial states (THPS) and their marginal distribution using the entangled state |ξ〉 representation. Also we obtain tomogram of THPS by virtue of the Radon transformation between the Wigner operator and the projection operator of another entangled state |η,τ ₁,τ ₂〉.     

A low temperature expansion for classicalN-vector models. II. Renormalization group equations

This paper continues the analysis of the low temperature expansions for classicalN-vector models started in [1]. A main part of it is a derivation of renormalization group equations and a construction of their solutions. To do this we have to introduce “a fluctuation integral” connected with a next renormalization transformation, and to make its preliminary analysis. The results of the paper are summarized in theorems stating that the renormalization transformation preserves the space of densitites, or actions described inductively in [1]. This work has been partially supported by the NSF Grant DMS-9102639.     

The phase diagram of random Boolean networks with nested canalizing functions

We obtain the phase diagram of random Boolean networks with nested canalizing functions. Using the annealed approximation, we obtain the evolution of the number b _t of nodes with value one, and the network sensitivity λ, and compare with numerical simulations of quenched networks. We find that, contrary to what was reported by Kauffman et al. [Proc. Natl. Acad. Sci. 101, 17102 (2004)], these networks have a rich phase diagram, were both the “chaotic" and frozen phases are present, as well as an oscillatory regime of the value of b _t . We argue that the presence of only the frozen phase in the work of Kauffman et al. was due simply to the specific parametrization used, and is not an inherent feature of this class of functions. However, these networks are significantly more stable than the variant where all possible Boolean functions are allowed.     

Field-theoretical Renormalization-Group approach to critical dynamics of crosslinked polymer blends

We consider a crosslinked polymer blend that may undergo a microphase separation. When the temperature is changed from an initial value towards a final one very close to the spinodal point, the mixture is out equilibrium. The aim is the study of dynamics at a given time t, before the system reaches its final equilibrium state. The dynamics is investigated through the structure factor, S(q, t), which is a function of the wave vector q, temperature T, time t, and reticulation dose D. To determine the phase behavior of this dynamic structure factor, we start from a generalized Langevin equation (model C) solved by the time composition fluctuation. Beside the standard de Gennes Hamiltonian, this equation incorporates a Gaussian local noise, ζ. First, by averaging over ζ, we get an effective Hamiltonian. Second, we renormalize this dynamic field theory and write a Renormalization-Group equation for the dynamic structure factor. Third, solving this equation yields the behavior of S(q, t), in space of relevant parameters. As result, S(q, t) depends on three kinds of lengths, which are the wavelength q ⁻¹, a time length scale R(t) ∼ t ^1/z , and the mesh size ξ ^*. The scale R(t) is interpreted as the size of growing microdomains at time t. When R(t) becomes of the order of ξ ^*, the dynamics is stopped. The final time, t ^*, then scales as t ^* ∼ ξ ^{* z}, with the dynamic exponent z = 6−η. Here, η is the usual Ising critical exponent. Since the final size of microdomains ξ ^* is very small (few nanometers), the dynamics is of short time. Finally, all these results we obtained from renormalization theory are compared to those we stated in some recent work using a scaling argument.     

Surface optical waves at the boundary with a nonlinear Kerr medium

A rigorous solution consistent with a plane wave approximation is given to the boundary problem for Maxwell’s equations for surface optical waves at the boundary with a nonlinear Kerr medium. Exact formulas for the flux intensity (J ₀) and energy density (W ₀) of these waves are derived depending on the parameters of the adjacent media and the propagation constant (ξ). It is shown that these variables as functions of ξ have minima. Thus, J ₀ and W ₀ increase sharply as the propagation constant deviates from the minimum value ξ_min. Their values are greater, the larger the difference between the dielectric constants of the linear and nonlinear media is. An expression for the propagation velocity of a nonlinear surface wave is also obtained.     

Density of states near the Anderson transition in a space of dimensionality d=4−ε

Asymptotically accurate results have been obtained for the average Green’s function and the density of states in a Gaussian random potential for dimensionality of space d=4−ε over the entire energy region, including the vicinity of the mobility threshold. For N∼1 (N is the order of the perturbation theory) only parquet terms corresponding to higher terms in 1/ε are taken into account. For large N all powers of 1/ε are taken into account with their coefficients calculated in the main asymptotic limit in N. This calculation is performed by combining the condition of renormalization theory with the Lipatov asymptotic limit. Zh. éksp. Teor. Fiz. 111, 1896–1914 (May 1997)     

The SUSY-QCD <Emphasis Type="Italic">β</Emphasis> function to three loops

A number of [` DR]\overline {\mbox {\textsc{D}R}} renormalization constants in softly broken SUSY- QCD are evaluated to three-loop level: the wave function renormalization constants for quarks, squarks, gluons, gluinos, ghosts, and ε-scalars, and the renormalization constants for the quark and gluino mass as well as for all cubic vertices. The latter allow us to derive the corresponding β functions through three loops, all of which we find to be identical to the expression for the gauge β function obtained by Jack et al. (Phys. Lett. B 386:138, 1996, ) (see also Pickering et al. in Phys. Lett. B 510, 347, 2001, ). This explicitly demonstrates the consistency of DRED with SUSY and gauge invariance, an important pre-requisite for precision calculations in supersymmetric theories.     

Slow relaxation experiments in disordered charge and spin density waves: collective dynamics of randomly distributed solitons

We show that the dynamics of disordered charge density waves (CDWs) and spin density waves (SDWs) is a collective phenomenon. The very low temperature specific heat relaxation experiments are characterized by: (i) “interrupted” ageing (meaning that there is a maximal relaxation time); and (ii) a broad power-law spectrum of relaxation times which is the signature of a collective phenomenon. We propose a random energy model that can reproduce these two observations and from which it is possible to obtain an estimate of the glass cross-over temperature (typically T _g≃ 100-200 mK). The broad relaxation time spectrum can also be obtained from the solutions of two microscopic models involving randomly distributed solitons. The collective behavior is similar to domain growth dynamics in the presence of disorder and can be described by the dynamical renormalization group that was proposed recently for the one dimensional random field Ising model [D.S. Fisher, P. Le Doussal, C. Monthus, Phys. Rev. Lett. 80, 3539 (1998)]. The typical relaxation time scales like ∼τexp(T _g/T). The glass cross-over temperature T_g related to correlations among solitons is equal to the average energy barrier and scales like T _g∼ 2xξΔ. x is the concentration of defects, ξ the correlation length of the CDW or SDW and Δ the charge or spin gap. Received 12 December 2001     

Criticality of the mean-field spin-boson model: boson state truncation and its scaling analysis

The spin-boson model has nontrivial quantum phase transitions at zero temperature induced by the spin-boson coupling. The bosonic numerical renormalization group (BNRG) study of the critical exponents β and δ of this model is hampered by the effects of boson Hilbert space truncation. Here we analyze the mean-field spin boson model to figure out the scaling behavior of magnetization under the cutoff of boson states N _b . We find that the truncation is a strong relevant operator with respect to the Gaussian fixed point in 0 < s < 1/2 and incurs the deviation of the exponents from the classical values. The magnetization at zero bias near the critical point is described by a generalized homogeneous function (GHF) of two variables τ = α – α _c and x = 1/N _b . The universal function has a double-power form and the powers are obtained analytically as well as numerically. Similarly, m(α = α _c ) is found to be a GHF of ϵ and x. In the regime s > 1/2, the truncation produces no effect. Implications of these findings to the BNRG study are discussed.