scientific article; zbMATH DE number 1256700
From MaRDI portal
Publication:4228436
zbMath0977.68538MaRDI QIDQ4228436
No author found.
Publication date: 20 January 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
A sharp threshold for a random constraint satisfaction problem, Waiter-client and client-waiter colourability and \(k\)-SAT games, Phase transitions in discrete structures, Sharp thresholds of graph properties, and the $k$-sat problem, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Many hard examples in exact phase transitions, A sharp threshold in proof complexity yields lower bounds for satisfiability search, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Super Solutions of Random Instances of Satisfiability, On the critical exponents of random k‐SAT, Two‐coloring random hypergraphs, The phase transition in random horn satisfiability and its algorithmic implications, An algorithm for random signed 3-SAT with intervals, On threshold properties of \(k\)-SAT: An additive viewpoint, Random Instances of Problems in NP – Algorithms and Statistical Physics, Phase transitions of PP-complete satisfiability problems, Phase transition in a random NK landscape model, The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘), 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, A general model and thresholds for random constraint satisfaction problems, Combinatorial sharpness criterion and phase transition classification for random CSPs, Proof of the satisfiability conjecture for large \(k\), Maximum independent sets on random regular graphs, Tail bounds for occupancy and the satisfiability threshold conjecture, Generating hard satisfiability problems, Unnamed Item, The number of satisfying assignments of random 2‐SAT formulas, Biased random k‐SAT, New Results on the Phase Transition for Random Quantified Boolean Formulas, One-step replica symmetry breaking of random regular NAE-SAT. II, Generalized satisfiability problems: Minimal elements and phase transitions., Exact enumeration of satisfiable 2-SAT formulae, Random 2 XORSAT phase transition, The asymptotic \(k\)-SAT threshold, CHAMP: a multipass algorithm for Max Sat based on saver variables, Threshold behaviors of a random constraint satisfaction problem with exact phase transitions, Go-MOCE: greedy order method of conditional expectations for Max Sat, On good algorithms for determining unsatisfiability of propositional formulas, The Satisfiability Threshold fork-XORSAT, On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., Satisfiability threshold for random XOR-CNF formulas, 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, Satisfiability threshold for power law random 2-SAT in configuration model, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, The satisfiability threshold for random linear equations, 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, Solution clustering in random satisfiability, A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas, On an online random k‐SAT model, Unnamed Item, Statistical mechanics methods and phase transitions in optimization problems, Rigorous results for random (\(2+p)\)-SAT, Random 2-SAT: Results and problems, 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, Bounding the scaling window of random constraint satisfaction problems, Satisfiability threshold for random regular \textsc{nae-sat}, Random 2-XORSAT at the Satisfiability Threshold, Probabilistic characterization of random Max \(r\)-Sat, The structure of the set of satisfying assignments for a random \(k\)-CNF, Unnamed Item, The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$, The SAT-UNSAT transition for random constraint satisfaction problems, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The probabilistic analysis of a greedy satisfiability algorithm, Length of prime implicants and number of solutions of random CNF formulae, The replica symmetric phase of random constraint satisfaction problems, Super solutions of random \((3 + p)\)-SAT, Random MAX SAT, random MAX CUT, and their phase transitions, Exact location of the phase transition for random (1,2)-QSAT, When does the giant component bring unsatisfiability?, On smoothed analysis in dense graphs and formulas, Complexity-theoretic models of phase transitions in search problems, Unnamed Item, Unnamed Item, Belief propagation on the random \(k\)-SAT model, Using the method of conditional expectations to supply an improved starting point for CCLS, The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas, 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, Walksat Stalls Well Below Satisfiability, Random 2-SAT and unsatisfiability, Solving non-uniform planted and filtered random SAT formulas greedily, A model of random industrial SAT
