Complexity-theoretic models of phase transitions in search problems
type: Item
instance of: scholarly article
title: Complexity-theoretic models of phase transitions in search problems
zbMATH Open document ID: 0949.68058
DOI: 10.1016/S0304-3975(00)00061-X
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 1521891
zbMATH Keywords: computational complexity
zbMATH Keywords: phase-transitions
zbMATH Keywords: search problems
author: Paul E. Dunne
author: A. Gibbons
author: Michele Zito
MaRDI profile type: Publication
cites work: Threshold functions
cites work: Q4012216
cites work: Q4228436
cites work: A Computing Procedure for Quantification Theory
cites work: Q3267900
cites work: Every monotone graph property has a sharp threshold
cites work: Hard random 3-SAT problems and the Davis-Putnam procedure
cites work: Q4198056
cites work: The satisfiability constraint gap
cites work: Phase transitions and the search problem
cites work: The hardest constraint problems: A double phase transition
cites work: Critical Behavior in the Satisfiability of Random Boolean Expressions
cites work: Approximating the unsatisfiability threshold of random formulas (Extended Abstract)
cites work: Q4123354
cites work: Average Case Complete Problems
cites work: On the greedy algorithm for satisfiability
cites work: Q4131648
cites work: Some Examples of Combinatorial Averaging
description: scientific article; zbMATH DE number 1521891