MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2017

2. Number - only D2

MPI-I-98-2-018

A note on the membership problem for the first elementary closure of a polyhedron

Eisenbrand, Friedrich

November 1998, 3 pages.

.
Status: distribution forbidden

The problem: Given an integral matrix $A$, an integral vector $b$ and some rational vector $x$, decide whether $x$ is outside the elementary closure $\{ x \in \R^n \mid Ax \leq b \}'$, is NP-complete. This result is achieved by an extension of a result by Caprara and Fischetti.