Hardness of monadic second-order formulae over succinct graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908761807912960 |
|---|---|
| author | Gamard, Guilhem Goubault-Larrecq, Aliénor Guillon, Pierre Ohlmann, Pierre Perrot, Kévin Theyssier, Guillaume |
| author_facet | Gamard, Guilhem Goubault-Larrecq, Aliénor Guillon, Pierre Ohlmann, Pierre Perrot, Kévin Theyssier, Guillaume |
| contents | Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_04522 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hardness of monadic second-order formulae over succinct graphs Gamard, Guilhem Goubault-Larrecq, Aliénor Guillon, Pierre Ohlmann, Pierre Perrot, Kévin Theyssier, Guillaume Computational Complexity Logic in Computer Science Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic. |
| title | Hardness of monadic second-order formulae over succinct graphs |
| topic | Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2302.04522 |