A sharp threshold in proof complexity yields lower bounds for satisfiability search

No abstract is available for this paper.

• Publication year

  2004

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2004-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcss.2003.07.011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• A machine program for theorem-proving

  2011cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006cited by this paper
• Random graphs

  2006cited by this paper
• The threshold for random k-SAT is 2^k log 2 - O(k)

  2004cited by this paper
• Lower bounds for random 3-SAT via differential equations

  2001influential reference
• Rigorous results for random (2+p)-SAT

  2001cited by this paper
• Short proofs are narrow—resolution made simple

  2001influential reference
• The phase transition in 1-in-k SAT and NAE 3-SAT

  2001cited by this paper
• Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems

  2000cited by this paper
• Trajectories in phase diagrams, growth processes, and computational complexity: how search algorithms solve the 3-satisfiability problem.

  2000cited by this paper
• Bounding the unsatisfiability threshold of random 3-SAT

  2000cited by this paper
• Random 3-SAT: The Plot Thickens

  2000cited by this paper
• Optimal myopic algorithms for random 3-SAT

  2000cited by this paper
• The scaling window of the 2‐SAT transition

  1999cited by this paper
• Symbolic Model Checking without BDDs

  1999cited by this paper
• 2+p‐SAT: Relation of typical‐case complexity to the nature of the phase transition

  1999cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• Threshold phenomena in random graph colouring and satisfiability

  1999cited by this paper
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

  1999cited by this paper
• Random Cnf’s are Hard for the Polynomial Calculus

  1999cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Boosting Combinatorial Search Through Randomization

  1998cited by this paper
• On the complexity of unsatisfiability proofs for random k-CNF formulas

  1998cited by this paper
• Rigorous Results for Random (2 + P)-sat

  1997cited by this paper
• Phase transition and search cost in the 2+p-sat problem

  1996cited by this paper
• Generating Hard Satisfiability Problems

  1996influential reference
• Analysis of Two Simple Heuristics on a Random Instance of k-SAT

  1996influential reference
• Pushing the Envelope: Planning, Propositional Logic and Stochastic Search

  1996cited by this paper
• Encoding Plans in Propositional Logic

  1996cited by this paper
• Generating Hard Satis ability Problems ?

  1995influential reference
• Critical Behavior in the Satisfiability of Random Boolean Expressions

  1994cited by this paper
• Domain-Independent Extensions to GSAT: Solving Large Structured Satisfiability Problems

  1993cited by this paper
• A Threshold for Unsatisfiability

  1992cited by this paper
• Mick gets some (the odds are on his side) (satisfiability)

  1992cited by this paper
• A New Method for Solving Hard Satisfiability Problems

  1992cited by this paper
• A New Method for Solving Hard Satis ability Problems

  1992cited by this paper
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem

  1990influential reference
• Surveys in Combinatorics, 1989: On the method of bounded differences

  1989cited by this paper
• Many hard examples for resolution

  1988cited by this paper
• Random Graphs

  1985cited by this paper
• Fast probabilistic algorithms for hamiltonian circuits and matchings

  1977cited by this paper
• A Computing Procedure for Quantification Theory

  1960cited by this paper

• Handbook of Satisfiability

  2021cites this paper
• Advice Complexity of Adaptive Priority Algorithms

  2019cites this paper
• Time and Space Bounds for Planning

  2017cites this paper
• Resolution Complexity of Random Constraint Satisfaction Problems

  2016cites this paper
• Cronfa - Swansea University Open Access Repository

  2014cites this paper
• Unified Characterisations of Resolution Hardness Measures

  2014cites this paper
• Unsatisfiability Bounds for Random Constraint Satisfaction Problems from an Energetic Interpolation Method

  2013cites this paper
• A New Upper Bound for Random (2 + P)-SAT by Flipping Two Variables

  2013cites this paper
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

  2012cites this paper
• Frozen variables in random boolean constraint satisfaction problems

  2012cites this paper
• Automata, Languages, and Programming

  2012cites this paper
• Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas

  2012influential citation
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

  2012influential citation
• Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method

  2012cites this paper
• Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic

  2011cites this paper
• The solution space geometry of random linear equations

  2011cites this paper
• Formula Caching in DPLL

  2010cites this paper
• Structure-based satisfiability checking

  2009cites this paper
• Empirical hardness models: Methodology and a case study on combinatorial auctions

  2009influential citation
• Handbook of satisfiability

  2009cites this paper
• Statistical and algebraic analysis of a family of random Boolean equations

  2009cites this paper
• A History of Satisfiability

  2009cites this paper
• Chapter 8 Random Satisfiability

  2008cites this paper
• A I ] 2 5 A pr 2 00 5 A New Class of Hard 3SAT Instances

  2008cites this paper
• A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems

  2008cites this paper
• Analyzing and Harnessing the Potential

  2008cites this paper
• Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

  2008cites this paper
• Threshold Phenomena in Random Constraint Satisfaction Problems

  2008cites this paper
• When does the giant component bring unsatisfiability?

  2008cites this paper
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

  2007cites this paper
• IMPACT OF RESTRICTED BRANCHING ON CLAUSE LEARNING SAT SOLVING

  2007cites this paper
• Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps

  2007cites this paper
• Satisfying assignments of Random Boolean CSP: Clusters and Overlaps

  2007cites this paper
• The Complexity of Propositional Proofs

  2007cites this paper
• Limitations of restricted branching in clause learning

  2007cites this paper
• A History of Satisfiability

  2007cites this paper
• Single-solution Random 3-SAT Instances

  2005cites this paper
• Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

  2004cites this paper
• The exact satisfiability threshold for a potentially intractable random constraint satisfaction problem

  2004cites this paper
• A Random Constraint Satisfaction Problem That Seems Hard for DPLL

  2004cites this paper