|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Schaefer's theorem for graphs | | Manuel Bodirsky
; Michael Pinsker
; | | Date: |
12 Nov 2010 | | 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 first-order 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 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 then classify the computational complexity of those
CSPs produces many statements of independent mathematical interest. | | Source: | arXiv, 1011.2894 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER