# Computational Short Cuts in Infinite Domain Constraint Satisfaction

arXiv: https://arxiv.org/abs/2211.10144 · HTML: https://mlsanity.com/paper/2211.10144/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 7 of its 55 references that are in the map.
- First posted on arXiv 18 Nov 2022.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

## Builds on (most cited first, 7 of 7)

- [Backdoors to Abduction](https://mlsanity.com/paper/1304.5961/) (2013)
- [Backdoors into Heterogeneous Classes of SAT and CSP](https://mlsanity.com/paper/1509.05725/) (2015)
- [An Algorithmic Theory of Integer Programming](https://mlsanity.com/paper/1904.01361/) (2019)
- [Parameterized Algorithms for MILPs with Small Treedepth](https://mlsanity.com/paper/1912.03501/) (2019)
- [On Backdoors To Tractable Constraint Languages](https://mlsanity.com/paper/1404.3675/) (2014)
- [Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting](https://mlsanity.com/paper/1507.02479/) (2015)
- [The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems](https://mlsanity.com/paper/1602.04353/) (2016)

## Abstract (arXiv)

A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (Proc. 42nd German Conference on AI (KI-2019)) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints -- this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.