Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908843851644928 |
|---|---|
| author | Geniet, Colin Goubault-Larrecq, Aliénor Perrot, Kévin |
| author_facet | Geniet, Colin Goubault-Larrecq, Aliénor Perrot, Kévin |
| contents | We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a counterpoint to Courcelle's theorem for graphs encoded by circuits, in two interplaying directions: (1) by allowing multiple binary relations, and (2) by restricting the interpretation of new symbols. Depending on the pair of an MSO problem $ψ$ and an MSO restriction $χ$, the problem is proven to be NP-hard or coNP-hard or P-hard, as long as $ψ$ is non-trivial on structures satisfying $χ$ with bounded clique-width. Indeed, there are P-complete problems (for logspace reductions) in our extended context. Finally, we strengthen a previous result on the necessity to parameterize the notion of non-triviality, hence supporting the choice of clique-width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18240 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions Geniet, Colin Goubault-Larrecq, Aliénor Perrot, Kévin Computational Complexity Discrete Mathematics Logic in Computer Science We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed as a counterpoint to Courcelle's theorem for graphs encoded by circuits, in two interplaying directions: (1) by allowing multiple binary relations, and (2) by restricting the interpretation of new symbols. Depending on the pair of an MSO problem $ψ$ and an MSO restriction $χ$, the problem is proven to be NP-hard or coNP-hard or P-hard, as long as $ψ$ is non-trivial on structures satisfying $χ$ with bounded clique-width. Indeed, there are P-complete problems (for logspace reductions) in our extended context. Finally, we strengthen a previous result on the necessity to parameterize the notion of non-triviality, hence supporting the choice of clique-width. |
| title | Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions |
| topic | Computational Complexity Discrete Mathematics Logic in Computer Science |
| url | https://arxiv.org/abs/2602.18240 |