A threshold for unsatisfiability
From MaRDI portal
Publication:676451
DOI10.1006/JCSS.1996.0081zbMATH Open0870.68077OpenAlexW2018251959WikidataQ56288408 ScholiaQ56288408MaRDI QIDQ676451FDOQ676451
Publication date: 18 March 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1996.0081
Recommendations
Cited In (75)
- A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES
- GD-SAT model and crossover line
- Title not available (Why is that?)
- Random 2-XORSAT at the Satisfiability Threshold
- Another look at the phenomenon of phase transition
- Branching Process Approach for 2-Sat Thresholds
- Satisfiability threshold for power law random 2-SAT in configuration model
- An Upper Bound on the Space Complexity of Random Formulae in Resolution
- Rényi entropies as a measure of the complexity of counting problems
- On the concentration of the number of solutions of random satisfiability formulas
- Statistical mechanics methods and phase transitions in optimization problems
- Super solutions of random \((3 + p)\)-SAT
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- A sharp threshold for a random constraint satisfaction problem
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- Random 2-SAT and unsatisfiability
- A perspective on certain polynomial-time solvable classes of satisfiability
- A model of random industrial SAT
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- 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
- 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
- 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
- Testing satisfiability of CNF formulas by computing a stable set of points
- Tensor network contractions for \#SAT
- How Many Conflicts Does It Need to Be Unsatisfiable?
- Delaying satisfiability for random 2SAT
- The number of 2-SAT functions
- Title not available (Why is that?)
- The cook-book approach to the differential equation method
- The Satisfiability Threshold fork-XORSAT
- On the threshold of intractability
- Phase transition in a random NK landscape model
- The phase transition in random horn satisfiability and its algorithmic implications
- Random 2 XORSAT phase transition
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- Lower bounds for random 3-SAT via differential equations
- Regular random \(k\)-SAT: Properties of balanced formulas
- A remark on random 2-SAT
- An Empirical Study of MAX-2-SAT Phase Transitions
- Exact location of the phase transition for random (1,2)-QSAT
- The number of satisfying assignments of random 2‐SAT formulas
- Title not available (Why is that?)
- Phase transitions of PP-complete satisfiability problems
- CHAMP: a multipass algorithm for Max Sat based on saver variables
- On the freezing of variables in random constraint satisfaction problems
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- Go-MOCE: greedy order method of conditional expectations for Max Sat
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Selecting Complementary Pairs of Literals
- When does the giant component bring unsatisfiability?
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Belief propagation on the random \(k\)-SAT model
- Weak lumpability in the \(k\)-SAT problem
- Generalized satisfiability problems: Minimal elements and phase transitions.
- On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT
- The scaling window of the 2-SAT transition
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)
