Determining computational complexity from characteristic ‘phase transitions’

DOI10.1038/22055zbMath1369.68244WikidataQ59066488 ScholiaQ59066488MaRDI QIDQ5354392

Lidror Troyansky, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Remi Monasson

Publication date: 1 September 2017

Published in: Nature (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1038/22055

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

82C44: Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

65Y20: Complexity and performance of numerical algorithms

Related Items

Complexity of Coloring Random Graphs, Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One, Phase Transition for Maximum Not-All-Equal Satisfiability, A hard-sphere model on generalized Bethe lattices: dynamics, Unnamed Item, Accessibility measure for eternal inflation: dynamical criticality and higgs metastability, Satisfiability transition in asymmetric neural networks, Disordered systems insights on computational hardness, On the Marchenko–Pastur law in analog bipartite spin-glasses, Gradient descent dynamics and the jamming transition in infinite dimensions, Mean field theory of jamming of nonspherical particles, Search optimization, funnel topography, and dynamical criticality on the string landscape, Early-time measure in eternal inflation, A random energy approach to deep learning, Dreaming neural networks: rigorous results, Towards backbone computing: A Greedy-Whitening based approach, Constructing concrete hard instances of the maximum independent set problem, Statistical and algebraic analysis of a family of random Boolean equations, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, Unnamed Item, Counting over non-planar graphs, Statistical mechanics methods and phase transitions in optimization problems, A physicist's approach to number partitioning, Rigorous results for random (\(2+p)\)-SAT, Lower bounds for random 3-SAT via differential equations, Upper bounds on the satisfiability threshold, Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs, Frozen development in graph coloring, Satisfiability threshold for random regular \textsc{nae-sat}, Replica theory for Levy spin glasses, Comparing dynamics: deep neural networks versus glassy systems, Critical properties of the SAT/UNSAT transitions in the classification problem of structured data, Anderson transition on the Bethe lattice: an approach with real energies, Complexity of Stability., Algorithms for computing minimal equivalent subformulas, Constraint acquisition, Gap theorems for robust satisfiability: Boolean CSPs and beyond, When a genetic algorithm outperforms hill-climbing, On the thresholds in linear and nonlinear Boolean equations, Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble, Problem difficulty for tabu search in job-shop scheduling, Fast and optimal decoding for machine translation, Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability, Generic properties of a computational task predict human effort and performance, Identifying and exploiting problem structures using explanation-based constraint programming, Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation, Computational complexity of some restricted instances of 3-SAT, Tensor network contractions for \#SAT, Backbone analysis and algorithm design for the quadratic assignment problem, Computational complexity of quantified Boolean formulas with fixed maximal deficiency, Phase transitions for Gödel incompleteness, Linear CNF formulas and satisfiability, (2+\(f\)(\(n\)))-SAT and its properties., On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem, Measuring instance difficulty for combinatorial optimization problems, Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT, An information-based neural approach to generic constraint satisfaction., A sharp threshold in proof complexity yields lower bounds for satisfiability search, The opacity of backbones, SAT competition 2020, Optimization of mean-field spin glasses, On the hierarchical community structure of practical Boolean formulas, On non-negative solutions to large systems of random linear equations, Complexity of stability, Group planning with time constraints, On the hardness of solving edge matching puzzles as SAT or CSP problems, Many hard examples in exact phase transitions, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, Sensor networks and distributed CSP: communication, computation and complexity, Pairs of SAT-assignments in random Boolean formulæ, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem, The cavity method for the rigidity transition, Phase transitions and symmetry breaking in genetic algorithms with crossover, On the complexity of unfrozen problems, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, SAT distributions with planted assignments and phase transitions between decision and optimization problems, Typical case complexity of satisfiability algorithms and the threshold phenomenon, The state of SAT, Regular-SAT: A many-valued approach to solving combinatorial problems, An Information-Based Neural Approach to Constraint Satisfaction, Phase transition and finite-size scaling for the integer partitioning problem, Canonical failure modes of real-time control systems: insights from cognitive theory, Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions, On the concentration of the number of solutions of random satisfiability formulas, Colloquium: Quantum annealing and analog quantum computation, Calculation of the 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz, Local entropy as a measure for sampling solutions in constraint satisfaction problems, On the quantum spin glass transition on the Bethe lattice, Statistical mechanics of complex economies, Phase transitions in integer linear problems, Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension, Decomposing SAT Instances with Pseudo Backbones, Satisfying constraint sets through convex envelopes, SAT Distributions with Phase Transitions between Decision and Optimization Problems, An efficient local search method for random 3-satisfiability, Des explications pour reconnaître et exploiter les structures cachées d'un problème combinatoire