Determining computational complexity from characteristic ‘phase transitions’
From MaRDI portal
Publication:5354392
DOI10.1038/22055zbMath1369.68244OpenAlexW1650993530WikidataQ59066488 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
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)
Related Items
Generic properties of a computational task predict human effort and performance, Many hard examples in exact phase transitions, A sharp threshold in proof complexity yields lower bounds for satisfiability search, Satisfiability transition in asymmetric neural networks, On non-negative solutions to large systems of random linear equations, 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, The state of SAT, Regular-SAT: A many-valued approach to solving combinatorial problems, Identifying and exploiting problem structures using explanation-based constraint programming, Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation, On the concentration of the number of solutions of random satisfiability formulas, When a genetic algorithm outperforms hill-climbing, Computational complexity of some restricted instances of 3-SAT, Complexity of Coloring Random Graphs, Tensor network contractions for \#SAT, On the thresholds in linear and nonlinear Boolean equations, Early-time measure in eternal inflation, A random energy approach to deep learning, (2+\(f\)(\(n\)))-SAT and its properties., On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., Des explications pour reconnaître et exploiter les structures cachées d'un problème combinatoire, Algorithms for computing minimal equivalent subformulas, Dreaming neural networks: rigorous results, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, 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, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, Sensor networks and distributed CSP: communication, computation and complexity, Towards backbone computing: A Greedy-Whitening based approach, 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, Constructing concrete hard instances of the maximum independent set problem, Complexity of stability, Constraint acquisition, An Information-Based Neural Approach to Constraint Satisfaction, Backbone analysis and algorithm design for the quadratic assignment problem, Computational complexity of quantified Boolean formulas with fixed maximal deficiency, Complexity of Stability., Group planning with time constraints, Gap theorems for robust satisfiability: Boolean CSPs and beyond, Pairs of SAT-assignments in random Boolean formulæ, Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem, Measuring instance difficulty for combinatorial optimization problems, The cavity method for the rigidity transition, Phase transition and finite-size scaling for the integer partitioning problem, Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble, 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, Counting over non-planar graphs, Phase transitions and symmetry breaking in genetic algorithms with crossover, 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, Canonical failure modes of real-time control systems: insights from cognitive theory, Satisfiability threshold for random regular \textsc{nae-sat}, Phase transitions for Gödel incompleteness, Colloquium: Quantum annealing and analog quantum computation, A hard-sphere model on generalized Bethe lattices: dynamics, The opacity of backbones, Statistical and algebraic analysis of a family of random Boolean equations, SAT competition 2020, Satisfiability by Maxwell-Boltzmann and Bose-Einstein Statistical Distributions, Linear CNF formulas and satisfiability, Optimization of mean-field spin glasses, Unnamed Item, Replica theory for Levy spin glasses, Comparing dynamics: deep neural networks versus glassy systems, Satisfying constraint sets through convex envelopes, An information-based neural approach to generic constraint satisfaction., Critical properties of the SAT/UNSAT transitions in the classification problem of structured data, Unnamed Item, On the hardness of solving edge matching puzzles as SAT or CSP problems, 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, Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem, SAT Distributions with Phase Transitions between Decision and Optimization Problems, An efficient local search method for random 3-satisfiability, Anderson transition on the Bethe lattice: an approach with real energies, 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, Accessibility measure for eternal inflation: dynamical criticality and higgs metastability, On the hierarchical community structure of practical Boolean formulas
