Critical Behavior in the Satisfiability of Random Boolean Expressions
From MaRDI portal
Publication:3101335
Recommendations
- On the critical exponents of random k‐SAT
- Threshold properties of random Boolean constraint satisfaction problems
- New Results on the Phase Transition for Random Quantified Boolean Formulas
- Stochastic Boolean satisfiability
- Stochastic Boolean satisfiability
- Criticality and heterogeneity in the solution space of random constraint satisfaction problems
- Truth-content and phase transitions of random Boolean networks with generic logics
- scientific article; zbMATH DE number 1305521
Cited in
(83)- Modelling the dynamics of stochastic local search on \(k\)-SAT
- 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
- Pairs of SAT-assignments in random Boolean formulæ
- On the thresholds in linear and nonlinear Boolean equations
- Phase transitions of EXPSPACE-complete problems: a further step
- A hard-sphere model on generalized Bethe lattices: dynamics
- Threshold properties of random Boolean constraint satisfaction problems
- The satisfiability threshold for random linear equations
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- On the survey-propagation equations in random constraint satisfiability problems
- Tensor network contractions for \#SAT
- PhysComp96. Proceedings of the 4th workshop on physics and computation, Boston, MA, USA, November 22--24, 1996
- Critical density thresholds in distributed wireless networks
- scientific article; zbMATH DE number 5547881 (Why is no real title available?)
- (2+\(f\)(\(n\)))-SAT and its properties.
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- Bounding the scaling window of random constraint satisfaction problems
- Accelerating a continuous-time analog SAT solver using GPUs
- The TSP phase transition
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- The asymptotic \(k\)-SAT threshold
- String matching and 1d lattice gases
- Coreduction homology algorithm
- Locating the phase transition in binary constraint satisfaction problems
- Local search for Boolean satisfiability with configuration checking and subscore
- Implicates and prime implicates in random 3-SAT
- Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- Generalized satisfiability problems: Minimal elements and phase transitions.
- Critical behavior in the computational cost of satisfiability testing
- Computational complexity of the landscape. I.
- Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
- An experimental study of operator choices in the \((1+(\lambda,\lambda))\) genetic algorithm
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
- Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation
- Delaying satisfiability for random 2SAT
- Phase transitions and the search problem
- Complexity-theoretic models of phase transitions in search problems
- Hard random 3-SAT problems and the Davis-Putnam procedure
- Random subcube intersection graphs. I: Cliques and covering
- On the quantum spin glass transition on the Bethe lattice
- Sharp thresholds of graph properties, and the $k$-sat problem
- Statistical mechanics methods and phase transitions in optimization problems
- Problem structure heuristics and scaling behavior for genetic algorithms
- On the satisfiability threshold of formulas with three literals per clause
- Resolving Braess's paradox in random networks
- Generating hard satisfiability problems
- An empirical study of phase transitions in binary constraint satisfaction problems
- Experimental results on the crossover point in random 3-SAT
- Phase transition and finite-size scaling in the vertex-cover problem
- Quantum optimization
- Random subcubes as a toy model for constraint satisfaction problems
- Secure information hiding based on computationally intractable problems
- scientific article; zbMATH DE number 1369843 (Why is no real title available?)
- An efficient local search method for random 3-satisfiability
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
- Entropy of theK-Satisfiability Problem
- On the concentration of the number of solutions of random satisfiability formulas
- SAT distributions with planted assignments and phase transitions between decision and optimization problems
- The scaling window of the 2-SAT transition
- A framework for structured quantum search.
- Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
- The phase transition in random horn satisfiability and its algorithmic implications
- Physics and complexity
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Plaquette models, cellular automata, and measurement-induced criticality
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Sufficient condition for polynomial solvability of random 3-CNF formulas
- Constructing concrete hard instances of the maximum independent set problem
- Gradient descent dynamics and the jamming transition in infinite dimensions
- Reduction-based MAX-3SAT with low nonlinearity and lattices under recombination
- Random matrix model of adiabatic quantum computing
- Error catastrophe for viruses infecting cells: analysis of the phase transition in terms of error classes
- A user authentication protocol based on the intractability of the 3-coloring problem
- Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One
- SAT Distributions with Phase Transitions between Decision and Optimization Problems
- GD-SAT model and crossover line
- Phase Transition for Maximum Not-All-Equal Satisfiability
- A new method for testing decision procedures in modal logics
- Biased random k‐SAT
This page was built for publication: Critical Behavior in the Satisfiability of Random Boolean Expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3101335)
