Phase transitions of PP-complete satisfiability problems. (Abstract)

MaRDI QIDQ2741517zbMATH OpenFDO

Authors Delbert D. Bailey, Víctor Dalmau, Phokion G. Kolaitis

Publication date 24 September 2001

zbMATH Keywords

complexityDavis-Putnam-Logemann-Loveland (DPLL) procedure

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Phase transitions of PP-complete satisfiability problems
• scientific article; zbMATH DE number 1369843
• An Empirical Study of MAX-2-SAT Phase Transitions
• Complexity-theoretic models of phase transitions in search problems
• scientific article; zbMATH DE number 2083805

Cited in

(4)

• Phase transitions of PP-complete satisfiability problems
• Phase Transition for Maximum Not-All-Equal Satisfiability
• scientific article; zbMATH DE number 1369843 (Why is no real title available?)
• Computational complexity of queries based on itemsets

This page was built for publication: Phase transitions of PP-complete satisfiability problems. (Abstract)

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