New math shows difference in ordering constraints for puzzles
Separating Non-redundancy and Chain Length
Computational Complexity
Summary
When solving puzzles or problems that have many rules, sometimes some rules are leftovers or repeated. The paper looks at two ways to measure how big these puzzle-like problems can get before some rules are unnecessary. The authors found an example where one way to measure can be much bigger than the other, proving they are not always the same size. This helps better understand how the structure of these problems works.
What this means in practice
- •For optimization software engineers: Identify problem instances where constraint ordering affects problem size to optimize solver performance.
- •For database query planners: Improve query optimization by understanding when constraints imply others and how to order them efficiently.
A theory result. No direct application yet.
Authors
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Abstract
For a constraint satisfaction problem defined by a relation $R$, its non-redundancy $\text{NRD}(R,n)$ is the size of largest instance (as a function of the number $n$ of variables) for which no constraint is implied by the rest. Its chain length $\text{CL}(R,n)$ is the largest such instance where the constraints can be ordered so that no constraint is implied by the preceding ones. Clearly $\text{CL}(R,n) \ge \text{NRD}(R,n)$ but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which $\text{CL}(R,n) \ge ω(\text{NRD}(R,n))$.