A sharp threshold in proof complexity yields lower bounds for satisfiability search
type: Item
instance of: scholarly article
title: A sharp threshold in proof complexity yields lower bounds for satisfiability search
zbMATH Open document ID: 1093.03033
author: Yanyan Li
published in: Journal of Computer and System Sciences
publication date: 2004-11-22T00:00:00Z
full work available at URL: http://hdl.handle.net/1807/9460
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2117372
MaRDI profile type: Publication
OpenAlex ID: W2062671967
cites work: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
cites work: Lower bounds for random 3-SAT via differential equations
cites work: Rigorous results for random (\(2+p)\)-SAT
cites work: The threshold for random k-SAT is 2 k (ln 2 - O(k))
cites work: Q5429954
cites work: Q4004078
cites work: Q4542576
cites work: Short proofs are narrow—resolution made simple
cites work: Q3682518
cites work: The scaling window of the 2-SAT transition
cites work: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
cites work: Q4228436
cites work: Many hard examples for resolution
cites work: Q4473023
cites work: A machine program for theorem-proving
cites work: A Computing Procedure for Quantification Theory
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Analysis of Two Simple Heuristics on a Random Instance ofk-sat
cites work: A threshold for unsatisfiability
cites work: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
cites work: Bounding the unsatisfiability threshold of random 3-SAT
cites work: Critical Behavior in the Satisfiability of Random Boolean Expressions
cites work: Q3496342
cites work: Q4704799
cites work: Determining computational complexity from characteristic ‘phase transitions’
cites work: Generating hard satisfiability problems
DOI: 10.1016/J.JCSS.2003.07.011
description: scientific article; zbMATH DE number 2117372