A threshold for unsatisfiability
From MaRDI portal
Publication:676451
DOI10.1006/jcss.1996.0081zbMath0870.68077OpenAlexW2018251959WikidataQ56288408 ScholiaQ56288408MaRDI QIDQ676451
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
Related Items
GD-SAT model and crossover line, A sharp threshold for a random constraint satisfaction problem, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, A sharp threshold in proof complexity yields lower bounds for satisfiability search, The phase transition in random horn satisfiability and its algorithmic implications, An algorithm for random signed 3-SAT with intervals, Phase transitions of PP-complete satisfiability problems, Phase transition in a random NK landscape model, Regular random \(k\)-SAT: Properties of balanced formulas, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, On the concentration of the number of solutions of random satisfiability formulas, Unnamed Item, Combinatorial sharpness criterion and phase transition classification for random CSPs, Tensor network contractions for \#SAT, The number of satisfying assignments of random 2‐SAT formulas, New Results on the Phase Transition for Random Quantified Boolean Formulas, Generalized satisfiability problems: Minimal elements and phase transitions., Exact enumeration of satisfiable 2-SAT formulae, Random 2 XORSAT phase transition, CHAMP: a multipass algorithm for Max Sat based on saver variables, Go-MOCE: greedy order method of conditional expectations for Max Sat, The Satisfiability Threshold fork-XORSAT, On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., A remark on random 2-SAT, The cook-book approach to the differential equation method, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, The scaling window of the 2-SAT transition, Rényi entropies as a measure of the complexity of counting problems, Another look at the phenomenon of phase transition, Satisfiability threshold for power law random 2-SAT in configuration model, A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES, On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes, On the freezing of variables in random constraint satisfaction problems, Computational complexity of quantified Boolean formulas with fixed maximal deficiency, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Branching Process Approach for 2-Sat Thresholds, An Upper Bound on the Space Complexity of Random Formulae in Resolution, Unnamed Item, Sharp thresholds for constraint satisfaction problems and homomorphisms, Statistical mechanics methods and phase transitions in optimization problems, Rigorous results for random (\(2+p)\)-SAT, Results related to threshold phenomena research in satisfiability: Lower bounds, Lower bounds for random 3-SAT via differential equations, Upper bounds on the satisfiability threshold, Satisfiability threshold for random regular \textsc{nae-sat}, Random 2-XORSAT at the Satisfiability Threshold, Unnamed Item, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The replica symmetric phase of random constraint satisfaction problems, Super solutions of random \((3 + p)\)-SAT, Exact location of the phase transition for random (1,2)-QSAT, When does the giant component bring unsatisfiability?, Unnamed Item, Unnamed Item, Weak lumpability in the \(k\)-SAT problem, Delaying satisfiability for random 2SAT, Belief propagation on the random \(k\)-SAT model, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Resolution complexity of random constraint satisfaction problems: Another half of the story, Selecting Complementary Pairs of Literals, An Empirical Study of MAX-2-SAT Phase Transitions, A perspective on certain polynomial-time solvable classes of satisfiability, A model of random industrial SAT
