Finite-certificate conjecture for relaxation complexity in dimension three

Let X\mathdsZ3X \subseteq \mathds{Z}^3 be a full-dimensional lattice-convex set, and let rc(X,Y)\operatorname{rc}(X,Y) denote the relaxation complexity of XX relative to a finite set Y\mathdsZ3XY \subseteq \mathds{Z}^3 \setminus X.

Finite-certificate conjecture. There exists a finite set Y\mathdsZ3XY \subseteq \mathds{Z}^3 \setminus X such that

rc(X)=rc(X,Y).\operatorname{rc}(X)=\operatorname{rc}(X,Y).

The preceding result gives a lower bound for the relaxation complexity of full-dimensional lattice-convex sets in dimension three, but does not provide a finite certificate for its exact value. This conjecture asserts that such a finite certificate always exists in dimension three.

Sources & referencesView supporting material

Primary source

Gennadiy Averkov, Christopher Hojny and Matthias Schymura, “Computational Aspects of Relaxation Complexity: Possibilities and Limitations”, arXiv:2105.12509 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.