A sharp threshold for a random constraint satisfaction problem
type: Item
instance of: scholarly article
title: A sharp threshold for a random constraint satisfaction problem
zbMATH Open document ID: 1121.68407
author: Abraham D. Flaxman
published in: Discrete Mathematics
publication date: 2004-08-19T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2092843
zbMATH Keywords: Random structures
zbMATH Keywords: Constraint satisfaction
zbMATH Keywords: Threshold phenomena
zbMATH Keywords: Phase transition
MaRDI profile type: Publication
full work available at URL: j.disc.2004.05.002
OpenAlex ID: W2164753468
cites work: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
cites work: The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
cites work: On the 2-colorability of random hypergraphs
cites work: The threshold for random k-SAT is 2 k (ln 2 - O(k))
cites work: Q3140436
cites work: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
cites work: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
cites work: Q4228436
cites work: Generalized satisfiability problems: Minimal elements and phase transitions.
cites work: Q4952608
cites work: Random 2-SAT: Results and problems
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Q4828949
cites work: Analysis of Two Simple Heuristics on a Random Instance ofk-sat
cites work: Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
cites work: A threshold for unsatisfiability
cites work: Bounding the unsatisfiability threshold of random 3-SAT
cites work: Q4411392
cites work: Random 2-SAT and unsatisfiability
cites work: Q4954175
DOI: 10.1016/J.DISC.2004.05.002
description: scientific article; zbMATH DE number 2092843