scientific article; zbMATH DE number 1256700

MaRDI QIDQ4228436zbMATH OpenFDO

Authors

Publication date 20 January 2002

zbMATH Keywords

truth assignment

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• On the maximum satisfiability of random formulas
• A threshold for unsatisfiability
• A threshold for unsatisfiability
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cited in

(only showing first 100 items - show all)

• The SAT-UNSAT transition for random constraint satisfaction problems
• When does the giant component bring unsatisfiability?
• Length of prime implicants and number of solutions of random CNF formulae
• Generalized satisfiability problems: Minimal elements and phase transitions.
• On good algorithms for determining unsatisfiability of propositional formulas
• On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
• Complexity-theoretic models of phase transitions in search problems
• Random 2-SAT and unsatisfiability
• Phase transitions in discrete structures
• A perspective on certain polynomial-time solvable classes of satisfiability
• A sharp threshold for a random constraint satisfaction problem
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• Satisfiability threshold for random XOR-CNF formulas
• A remark on random 2-SAT
• The satisfiability threshold for random linear equations
• Probabilistic characterization of random Max r-Sat
• Belief propagation on the random \(k\)-SAT model
• Using the method of conditional expectations to supply an improved starting point for CCLS
• Solving non-uniform planted and filtered random SAT formulas greedily
• A model of random industrial SAT
• Proof of the satisfiability conjecture for large \(k\)
• Phase transition in matched formulas and a heuristic for biclique satisfiability
• Super solutions of random \((3 + p)\)-SAT
• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• Many hard examples in exact phase transitions
• Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
• Phase transition in a random NK landscape model
• Maximum independent sets on random regular graphs
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• 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
• An algorithm for random signed 3-SAT with intervals
• Phase transitions of PP-complete satisfiability problems
• Generating hard satisfiability problems
• CHAMP: a multipass algorithm for Max Sat based on saver variables
• Go-MOCE: greedy order method of conditional expectations for Max Sat
• The scaling window of the 2-SAT transition
• Thresholds for colourability and satisfiability in random graphs and Boolean formulae
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Rényi entropies as a measure of the complexity of counting problems
• On smoothed analysis in dense graphs and formulas
• Selecting Complementary Pairs of Literals
• An Empirical Study of MAX-2-SAT Phase Transitions
• Super solutions of random instances of satisfiability
• Random instances of problems in NP -- algorithms and statistical physics
• New Results on the Phase Transition for Random Quantified Boolean Formulas
• On the maximum satisfiability of random formulas
• A general model and thresholds for random constraint satisfaction problems
• Sharp thresholds of graph properties, and the k-sat problem
• Two‐coloring random hypergraphs
• The phase transition in random horn satisfiability and its algorithmic implications
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• The cook-book approach to the differential equation method
• Random MAX SAT, random MAX CUT, and their phase transitions
• On the critical exponents of random k‐SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• Tail bounds for occupancy and the satisfiability threshold conjecture
• Branching process approach for 2-SAT thresholds
• The replica symmetric phase of random constraint satisfaction problems
• Size, cost and capacity: a semantic technique for hard random QBFs
• A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
• The satisfiability threshold for non-uniform random 2-SAT
• Bounds on the satisfiability threshold for power law distributed random SAT
• Exact location of the phase transition for random (1,2)-QSAT
• Walksat Stalls Well Below Satisfiability
• Theory and Applications of Satisfiability Testing
• The satisfiability threshold for k-XORSAT
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
• A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
• On an online random k‐SAT model
• Random 2-XORSAT at the Satisfiability Threshold
• The probabilistic analysis of a greedy satisfiability algorithm
• Locally satisfiable formulas
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• Satisfiability threshold for power law random 2-SAT in configuration model
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• 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}
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• The number of satisfying assignments of random 2‐SAT formulas
• Biased random k‐SAT
• What is the satisfiability threshold of random balanced Boolean expressions?
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Exact enumeration of satisfiable 2-SAT formulae
• Random 2 XORSAT phase transition
• Polarised random k-SAT
• Searching for (sharp) thresholds in random structures: where are we now?
• Integrating multi-armed bandit with local search for MaxSAT

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228436)