Hardness of computing the dimension of an integral polytope?

Question

Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested in the hardness of computing the dimension of the polytope $P$.

Equivalently we can formulate this as the decision problem by asking whether the dimension of $P$ is $m$ for some $0 \leq m \leq n$. To prove that the dimension is indeed $m$, we need to show that

1. There are $m+1$ affinely independent vectors in $P$ which yields that the dimension is at least $m$.
2. There are $n-m$ independent equalities that are satisfied by $P$ which yields that the dimension is at most $m$.

I could not find any literature that considers this problem. Also I cannot think of a reduction to or from another problem.

---

Answer thanks to Neil Young:

• Condition 1 can be checked in polynomial time while this is not obvious for Condition 2. Therefore the problem "is the dimension of $P$ at least $m$?" is in NP and similarly the problem "is the dimension at most $m$?" is in co-NP.

• The decision problem "is $P$ empty?" is well known to be NP-hard. This problem can be reduced to the decision of dimension as follows: Add $m$ additional free variables to $P$ to obtain $P'$. Then $P$ is not empty iff the dimension of $P'$ is at least $m$. Therefore "is $P$ empty?" can be reduced to "is the dimension of $P'$ at least $m$?".

Together we obtain that "is the dimension of $P$ at least $m$?" is NP-complete and as a result that "is the dimension of $P$ equal $m$?" is NP-hard.

However, if we additionally assume that $P$ is non-empty then this reduction does not work. It is unclear to me whether the problem remains NP-complete.

(Edit thanks to Neal Young: Given a feasible solution, finding a second, different, feasible solution is NP-hard. And since two different vectors are affinely independent deciding "is the dimension of $P$ at least $1$?" is NP-hard for non-empty $P$. Again, by adding free variables, it follows that deciding "is dimension of $P$ at least $m$?" is NP-hard even for non-empty $P$)

---

Originally, my interest in this problem arose from studying the convex hull of the feasible set of an ILP corresponding to a combinatorial optimization problem. Such polytopes have some additional structure and the general "proof" from above does not hold. So my follow-up question is:

Are there examples of combinatorial optimization problems where it is hard to compute the dimension of the convex hull of all feasible solutions and where the set of feasible solutions is non-empty? And related: are there examples where it is hard to decide whether a valid inequality defines a facet (maybe even where the polytope is full dimensional and the facet has dimension $n-1$)?

Answer 1

Yes, MORE-SAT, defined below, is one example of a combinatorial optimization problem for which the natural 0/1 integer linear program (ILP) is guaranteed to be feasible, and determining the dimension of the convex hull of the feasible solutions is NP-hard.

Here is the definition of MORE-SAT: Given a satisfiable CNF formula, does it have more than one satisfying assignment?

Lemma 1. MORE-SAT is NP-complete.

We postpone the proof, which is a standard exercise.

Given a MORE-SAT instance $\phi$, let ILP$(\phi)$ represent its ILP formulation via the standard ILP for CNF-SAT. Then the number of satisfying assignments to $\phi$ equals the number of feasible points in ILP$(\phi)$, so ILP$(\phi)$ is guaranteed to be feasible, and it has more than one feasible solution iff $\phi$ has more than one satisfying assignment. So it is NP-hard to determine whether the dimension of the convex hull of the feasible points of ILP$(\phi)$ is at least 1.

Note that it follows that the following problem is NP-hard: Given a feasible 0/1 integer linear program, does it have more than one feasible solution?

Proof sketch for Lemma 1. Here is a reduction from CNF-SAT. Given a CNF-SAT instance $\phi$, let $x_i$ denote its $i$th variable and $C_i$ denote its $i$th clause. Introduce a new variable $y$, and define MORE-SAT instance $$\phi' = C'_1 \wedge C'_2 \wedge \cdots \wedge C'_m \wedge D_1 \wedge D_2 \wedge \cdots \wedge D_n$$ where $C'_i = C_i \vee y$ (for each clause $C_i$ of $\phi)$ and $D_i = x_i \vee \overline y$ (for each variable $x_i$ of $\phi$).

Then setting $x_1 = x_2 = \cdots = x_n = y = $ true gives one satisfying assignment to $\phi'$, and the satisfying assignments with $y=$ false are exactly those where the assignment to $x$ satisfies $\phi$. So the number of satisfying assignments for $\phi'$ is exactly one more than the number for $\phi$. In particular, $\phi'$ is satisfiable, and it has more than one satisfying assignment iff $\phi$ is satisfiable. $~~~\Box$

Remark 1. Given that there are apparently parsimonious polynomial-time reductions from CNF-SAT to most other "natural" NP-complete problems, it follows that, for those other NP-complete problems, the problem of determining whether there is more than one solution (even when there is guaranteed to be at least one) is NP-hard, and likewise for the natural ILP formulations of many of those problems, determining whether the dimension is at least 1 (even when the ILP is guaranteed to be feasible) is NP-hard.

Remark 2. It seems an easy exercise to generalize this to show that the following problem is NP-hard for any given $k\ge 0$: Given a 0/1 ILP such that the convex hull $P$ of its feasible solutions has dimension at least $k$, does $P$ have dimension at least $k+1$? (Reduce from CNF-SAT. Given $\phi$, apply the reduction in Lemma 1 to obtain MORE-SAT instance $\phi'$, and let $\pi$ be the standard ILP for $\phi'$. Then obtain ILP $\pi'$ from $\pi$ by adding $k$ new unconstrained 0/1 variables $Z_1, Z_2, \ldots, Z_{k}$. Then $\pi'$ will have $2^{k}$ solutions with $X_1 = \cdots = X_n = Y=$ 1 and the $Z$'s set arbitrarily, and these solutions have dimension $k$. And $\phi$ is satisfiable iff $\pi'$ has additional solutions with $Y=0$, which happens iff the dimension strictly exceeds $k$...)