|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Complexity of Boolean Constraint Isomorphism | | Elmar Böhler
; Edith Hemaspaandra
; Steffen Reith
; Heribert Vollmer
; | | Date: |
27 Jun 2003 | | Subject: | Computational Complexity; Logic in Computer Science ACM-class: F.1.3;F.4.1 | cs.CC cs.LO | | Abstract: | In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems (nowadays usually called Boolean constraint satisfaction problems) and showed that all these satisfiability problems are either in P or NP-complete. In recent years, similar results have been obtained for quite a few other problems for Boolean constraints.Almost all of these problems are variations of the satisfiability problem. In this paper, we address a problem that is not a variation of satisfiability, namely, the isomorphism problem for Boolean constraints. Previous work by Böhler et al. showed that the isomorphism problem is either coNP-hard or reducible to the graph isomorphism problem (a problem that is in NP, but not known to be NP-hard), thus distinguishing a hard case and an easier case. However, they did not classify which cases are truly easy, i.e., in P. This paper accomplishes exactly that. It shows that Boolean constraint isomorphism is coNP-hard (and GI-hard), or equivalent to graph isomorphism, or in P, and it gives simple criteria to determine which case holds. | | Source: | arXiv, cs.CC/0306134 | | 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