A threshold for unsatisfiability
From MaRDI portal
Recommendations
Cited in
(78)- The scaling window of the 2-SAT transition
- Rényi entropies as a measure of the complexity of counting problems
- On the concentration of the number of solutions of random satisfiability formulas
- GD-SAT model and crossover line
- Exact location of the phase transition for random \((1,2)\)-QSAT
- Super solutions of random \((3 + p)\)-SAT
- A sharp threshold for a random constraint satisfaction problem
- Statistical mechanics methods and phase transitions in optimization problems
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Random 2-SAT and unsatisfiability
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Bounds on the satisfiability threshold for power law distributed random SAT
- scientific article; zbMATH DE number 2090298 (Why is no real title available?)
- A perspective on certain polynomial-time solvable classes of satisfiability
- A model of random industrial SAT
- The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
- Random 2-XORSAT at the Satisfiability Threshold
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- Branching process approach for 2-SAT thresholds
- Satisfiability threshold for random regular \textsc{nae-sat}
- Upper bounds on the satisfiability threshold
- A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
- On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
- A new upper bound for random (2 + p)-SAT by flipping two variables
- The replica symmetric phase of random constraint satisfaction problems
- Resolution complexity of random constraint satisfaction problems: Another half of the story
- Exact enumeration of satisfiable 2-SAT formulae
- A threshold for unsatisfiability
- An algorithm for random signed 3-SAT with intervals
- Testing satisfiability of CNF formulas by computing a stable set of points
- Rigorous results for random (\(2+p)\)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
- New Results on the Phase Transition for Random Quantified Boolean Formulas
- Tensor network contractions for \#SAT
- Another look at the phenomenon of phase transition
- The cook-book approach to the differential equation method
- The number of 2-SAT functions
- Delaying satisfiability for random 2SAT
- How Many Conflicts Does It Need to Be Unsatisfiable?
- scientific article; zbMATH DE number 1369843 (Why is no real title available?)
- Random 2 XORSAT phase transition
- On the CNF-complexity of bipartite graphs containing no squares
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- Phase transition in a random NK landscape model
- The phase transition in random horn satisfiability and its algorithmic implications
- Regular random \(k\)-SAT: Properties of balanced formulas
- Lower bounds for random 3-SAT via differential equations
- A remark on random 2-SAT
- An Empirical Study of MAX-2-SAT Phase Transitions
- Unsatisfiable CNF formulas contain many conflicts
- The number of satisfying assignments of random 2‐SAT formulas
- Phase transitions of PP-complete satisfiability problems
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- On the freezing of variables in random constraint satisfaction problems
- The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Computational complexity of quantified Boolean formulas with fixed maximal deficiency
- Redundancy in logic. II: 2CNF and Horn propositional formulae
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
- The satisfiability threshold for \(k\)-XORSAT
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- When does the giant component bring unsatisfiability?
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Selecting Complementary Pairs of Literals
- scientific article; zbMATH DE number 1775484 (Why is no real title available?)
- Satisfiability threshold for power law random 2-SAT in configuration model
- scientific article; zbMATH DE number 7561554 (Why is no real title available?)
- Weak lumpability in the \(k\)-SAT problem
- Belief propagation on the random \(k\)-SAT model
- Generalized satisfiability problems: Minimal elements and phase transitions.
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
This page was built for publication: A threshold for unsatisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676451)
