{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigiztielur3k4rm7vkl2eblmgcgnto4cmuxv56mzgjcglthzq2som",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfj45b5osgz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.18240v1",
  "publishedAt": "2026-02-23T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Colin Geniet",
    "Aliénor Goubault-Larrecq",
    "Kévin Perrot"
  ],
  "textContent": "**Authors:** Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot\n\nWe 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"
}