  Automated program verification often proceeds by exhibiting inductive
invariants entailing the desired properties.For numerical properties, a
classical class of invariants is convex polyhedra: solution sets of system of
linear (in)equalities.Forty years of research on convex polyhedral invariants
have focused, on the one hand, on identifying "easier" subclasses, on the other
hand on heuristics for finding general convex polyhedra.These heuristics are
however not guaranteed to find polyhedral inductive invariants when they
exist.To our best knowledge, the existence of polyhedral inductive invariants
has never been proved to be undecidable.In this article, we show that the
existence of convex polyhedral invariants is undecidable, even if there is only
one control state in addition to the "bad" one.The question is still open if
one is not allowed any nonlinear constraint.

Programming Languages;Logic in Computer Science