Finite-certificate conjecture for relaxation complexity in dimension three
Finite-certificate conjecture for relaxation complexity in dimension three
Let be a full-dimensional lattice-convex set, and let denote the relaxation complexity of relative to a finite set .
Finite-certificate conjecture. There exists a finite set such that
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.