Name
Abstract | ||
|---|---|---|
Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial time, or is NP-complete. We present an analog of this dichotomy result for the propositional logic of graphs instead of Boolean logic. In this generalization of Schaefer's result, the input consists of a set W of variables and a conjunction Phi of statements ("constraints") about these variables in the language of graphs, where each statement is taken from a fixed finite set Psi of allowed quantifier-free first-order formulas; the question is whether Phi is satisfiable in a graph. We prove that either Psi is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. This is achieved by a universal-algebraic approach, which in turn allows us to use structural Ramsey theory. To apply the universal-algebraic approach, we formulate the computational problems under consideration as constraint satisfaction problems (CSPs) whose templates are first-order definable in the countably infinite random graph. Our method to classify the computational complexity of those CSPs produces many statements of independent mathematical interest. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2764899 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
dichotomy result,corresponding problem,computational problem,boolean logic,boolean constraint satisfaction problem,constraint satisfaction problem,polynomial time,complexity classification result,countably infinite random graph,universal-algebraic approach,propositional logic,satisfiability,constraint satisfaction problems,random graph,universal algebra,polymorphism,correspondence problem,first order,computational complexity,ramsey theory | Conference | 62 |
Issue | ISSN | Citations |
3 | 0004-5411 | 14 |
PageRank | References | Authors |
0.83 | 23 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Michael Pinsker | 2 | 132 | 17.54 |