  The relaxation complexity $\mathrm{rc}(X)$ of the set of integer points $X$
contained in a polyhedron is the smallest number of facets of any polyhedron
$P$ such that the integer points in $P$ coincide with $X$. It is a useful tool
to investigate the existence of compact linear descriptions of $X$. In this
article, we derive tight and computable upper bounds on
$\mathrm{rc}_{\mathbb{Q}}(X)$, a variant of $\mathrm{rc}(X)$ in which the
polyhedra $P$ are required to be rational, and we show that $\mathrm{rc}(X)$
can be computed in polynomial time if $X$ is 2-dimensional. Further, we
investigate computable lower bounds on $\mathrm{rc}(X)$ with the particular
focus on the existence of a finite set $Y \subseteq \mathbb{Z}^d$ such that
separating $X$ and $Y \setminus X$ allows us to deduce $\mathrm{rc}(X) \geq k$.
In particular, we show for some choices of $X$ that no such finite set $Y$
exists to certify the value of $\mathrm{rc}(X)$, providing a negative answer to
a question by Weltge (2015). We also obtain an explicit formula for
$\mathrm{rc}(X)$ for specific classes of sets $X$ and present the first
practically applicable approach to compute $\mathrm{rc}(X)$ for sets $X$ that
admit a finite certificate.
