<p>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.</p>
<p>Here is the definition of MORE-SAT: <em>Given a satisfiable CNF formula, does it have more than one satisfying assignment</em>?</p>
<p><strong>Lemma 1.</strong> <em>MORE-SAT is NP-complete.</em></p>
<p>We postpone the proof, which is a standard exercise.</p>
<p>Given a MORE-SAT instance <span class="math-container">$\phi$</span>, let ILP<span class="math-container">$(\phi)$</span> represent its ILP formulation via <a href="https://math.stackexchange.com/questions/2564236/how-can-i-formulate-the-3-sat-problem-as-a-0-1-linear-integer-program">the standard ILP for CNF-SAT</a>.  Then the number of satisfying assignments to <span class="math-container">$\phi$</span> equals the number of feasible points in ILP<span class="math-container">$(\phi)$</span>, so ILP<span class="math-container">$(\phi)$</span> is guaranteed to be feasible, and it has more than one feasible solution iff <span class="math-container">$\phi$</span> 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<span class="math-container">$(\phi)$</span> is at least 1.</p>
<p>Note that it follows that the following problem is NP-hard: <em>Given a feasible 0/1 integer linear program, does it have more than one feasible solution</em>?</p>
<p><em>Proof sketch for Lemma 1.</em>
Here is a reduction from CNF-SAT.  Given a CNF-SAT instance <span class="math-container">$\phi$</span>, let <span class="math-container">$x_i$</span> denote its <span class="math-container">$i$</span>th variable and <span class="math-container">$C_i$</span> denote its <span class="math-container">$i$</span>th clause.  Introduce a new variable <span class="math-container">$y$</span>, and define MORE-SAT instance <span class="math-container">$$\phi' = C'_1 \wedge C'_2 \wedge \cdots \wedge C'_m \wedge D_1 \wedge D_2 \wedge \cdots \wedge D_n$$</span>
where <span class="math-container">$C'_i = C_i \vee y$</span> (for each clause <span class="math-container">$C_i$</span> of <span class="math-container">$\phi)$</span> and <span class="math-container">$D_i = x_i \vee \overline y$</span> (for each variable <span class="math-container">$x_i$</span> of <span class="math-container">$\phi$</span>).</p>
<p>Then setting <span class="math-container">$x_1 = x_2 = \cdots = x_n = y = $</span> true gives one satisfying assignment to <span class="math-container">$\phi'$</span>, and the satisfying assignments with <span class="math-container">$y=$</span> false are exactly those where the assignment to <span class="math-container">$x$</span> satisfies <span class="math-container">$\phi$</span>.  So the number of satisfying assignments for <span class="math-container">$\phi'$</span> is exactly one more than the number for <span class="math-container">$\phi$</span>.  In particular, <span class="math-container">$\phi'$</span> is satisfiable, and it has more than one satisfying assignment iff <span class="math-container">$\phi$</span> is satisfiable. <span class="math-container">$~~~\Box$</span></p>
<p><strong>Remark 1.</strong> Given that there are <a href="https://cs.stackexchange.com/questions/77957/there-are-parsimonious-reductions-between-all-np-complete-problems-well-known-c">apparently</a> parsimonious polynomial-time reductions from CNF-SAT to most other &quot;natural&quot; 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.</p>
<p><strong>Remark 2.</strong> It seems an easy exercise to generalize this to show that the following problem is NP-hard for any given <span class="math-container">$k\ge 0$</span>: <em>Given a 0/1 ILP such that the convex hull <span class="math-container">$P$</span> of its feasible solutions has dimension at least <span class="math-container">$k$</span>, does <span class="math-container">$P$</span> have dimension at least <span class="math-container">$k+1$</span>?</em>  (Reduce from CNF-SAT.  Given <span class="math-container">$\phi$</span>, apply the reduction in Lemma 1 to obtain MORE-SAT instance <span class="math-container">$\phi'$</span>, and let <span class="math-container">$\pi$</span> be the standard ILP for <span class="math-container">$\phi'$</span>. Then obtain ILP <span class="math-container">$\pi'$</span> from <span class="math-container">$\pi$</span> by adding <span class="math-container">$k$</span> new unconstrained 0/1 variables <span class="math-container">$Z_1, Z_2, \ldots, Z_{k}$</span>.  Then <span class="math-container">$\pi'$</span> will have <span class="math-container">$2^{k}$</span> solutions with <span class="math-container">$X_1 = \cdots = X_n = Y=$</span> 1 and the <span class="math-container">$Z$</span>'s set arbitrarily, and these solutions have dimension <span class="math-container">$k$</span>.  And <span class="math-container">$\phi$</span> is satisfiable iff <span class="math-container">$\pi'$</span> has additional solutions with <span class="math-container">$Y=0$</span>, which happens iff the dimension strictly exceeds <span class="math-container">$k$</span>...)</p>

CC BY-SA 4.0
2021-11-12T16:14:06.647Z
2021-11-13T21:31:42.590Z
2021-11-13T21:31:42.590Z
Neal Young
<p>Given a set of linear inequalities <span class="math-container">$Ax \leq b$</span> let <span class="math-container">$P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$</span> 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 <span class="math-container">$P$</span>.</p>
<p>Equivalently we can formulate this as the decision problem by asking whether the dimension of <span class="math-container">$P$</span> is <span class="math-container">$m$</span> for some <span class="math-container">$0 \leq m \leq n$</span>.
To prove that the dimension is indeed <span class="math-container">$m$</span>, we need to show that</p>
<ol>
<li>There are <span class="math-container">$m+1$</span> affinely independent vectors in <span class="math-container">$P$</span> which yields that the dimension is at least <span class="math-container">$m$</span>.</li>
<li>There are <span class="math-container">$n-m$</span> independent equalities that are satisfied by <span class="math-container">$P$</span> which yields that the dimension is at most <span class="math-container">$m$</span>.</li>
</ol>
<p>I could not find any literature that considers this problem. Also I cannot think of a reduction to or from another problem.</p>
<hr />
<p>Answer thanks to Neil Young:</p>
<ul>
<li><p>Condition 1 can be checked in polynomial time while this is not obvious for Condition 2.
Therefore the problem &quot;is the dimension of <span class="math-container">$P$</span> at least <span class="math-container">$m$</span>?&quot; is in NP and similarly the problem &quot;is the dimension at most <span class="math-container">$m$</span>?&quot; is in co-NP.</p>
</li>
<li><p>The decision problem &quot;is <span class="math-container">$P$</span> empty?&quot; is well known to be NP-hard. This problem can be reduced to the decision of dimension as follows: Add <span class="math-container">$m$</span> additional free variables to <span class="math-container">$P$</span> to obtain <span class="math-container">$P'$</span>. Then <span class="math-container">$P$</span> is not empty iff the dimension of <span class="math-container">$P'$</span> is at least <span class="math-container">$m$</span>. Therefore &quot;is <span class="math-container">$P$</span> empty?&quot; can be reduced to &quot;is the dimension of <span class="math-container">$P'$</span> at least <span class="math-container">$m$</span>?&quot;.</p>
</li>
</ul>
<p>Together we obtain that &quot;is the dimension of <span class="math-container">$P$</span> at least <span class="math-container">$m$</span>?&quot; is NP-complete and as a result that &quot;is the dimension of <span class="math-container">$P$</span> equal <span class="math-container">$m$</span>?&quot; is NP-hard.</p>
<p>However, if we additionally assume that <span class="math-container">$P$</span> is non-empty then this reduction does not work. It is unclear to me whether the problem remains NP-complete.</p>
<p>(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 &quot;is the dimension of <span class="math-container">$P$</span> at least <span class="math-container">$1$</span>?&quot; is NP-hard for non-empty <span class="math-container">$P$</span>. Again, by adding free variables, it follows that deciding &quot;is dimension of <span class="math-container">$P$</span> at least <span class="math-container">$m$</span>?&quot; is NP-hard even for non-empty <span class="math-container">$P$</span>)</p>
<hr />
<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 &quot;proof&quot; from above does not hold.
So my <strong>follow-up question</strong> is:</p>
<p>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 <span class="math-container">$n-1$</span>)?</p>

CC BY-SA 4.0
2021-11-11T14:16:37.443Z
Surely it's NP-hard, because determining whether an ILP is even feasible is NP-hard.  Do you know whether the decision problem "is the dimension at least $m$"? is in NP?  (At first glance, you could just guess a set of vectors for Condition 1 and check them... but you'd need to know that it suffices to consider vectors with encoding size polynomial in the encoding size of $(A, b)$...)  If that problem is in NP, then your problem should be in [DP](https://complexityzoo.net/Complexity_Zoo:D#dp) (expressible as the intersection of languages in NP and coNP).
Neal Young
CC BY-SA 4.0
2021-11-11T15:38:19.593Z
In my case I was thinking about bounded polytopes, even more specifically about 01-polytopes $P \subseteq \{0,1\}^n$. In that case a certificate for Conditions 1 and 2 can clearly be encoded in polynomial size and the problem is in NP. I am not sure about unbounded polyhedra.
badboul
CC BY-SA 4.0
2021-11-11T15:44:58.703Z
Also in my case the polytopes are nonempty. Maybe the hardness of the decision problem "given $k$ affinely independent vectors in $P$, does there exist an additional vector that is affinely independent of the given $k$?" can be established by a reduction from feasibility of an ILP. Thanks for the pointer.
badboul
CC BY-SA 4.0
2021-11-11T19:17:31.680Z
(i) How do you verify (in NP) Condition 2 for a given set of equalities even in the 0/1 case (given that you need to check whether all integer points in P satisfy those inequalities)?  The problem "Does a given ILP polytope have dimension at most $k$" seems co-NP hard, e.g. by reduction from UNSAT.  (ii)  By "an additional vector that..." do you mean "an additional vector in P that..."?  (iii)  Assuming so, the case k=0 is testing whether P is empty (NP-hard), and it seems likely that the cases k >= 1 can be reduced to from any given polytope just by adding some artificial variables...
Neal Young
CC BY-SA 4.0
2021-11-12T02:53:28.453Z
Please [edit] your question to include all relevant information, such as that you are working over $\{0,1\}^n$.  People shouldn't have to read the comments to understand what you are asking.
D.W.
<np-hardness><integer-programming><polytope>
Hardness of computing the dimension of an integral polytope?
badboul
# Hardness of computing the dimension of an integral polytope?

(Asked by: username_0 on 2021-11-11)

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$)?

**Tags:** np-hardness, integer-programming, polytope
> **Comments:**
> **username_1**: Surely it's NP-hard, because determining whether an ILP is even feasible is NP-hard.  Do you know whether the decision problem "is the dimension at least $m$"? is in NP?  (At first glance, you could just guess a set of vectors for Condition 1 and check them... but you'd need to know that it suffices to consider vectors with encoding size polynomial in the encoding size of $(A, b)$...)  If that problem is in NP, then your problem should be in [DP](https://complexityzoo.net/Complexity_Zoo:D#dp) (expressible as the intersection of languages in NP and coNP).  
> **username_0**: In my case I was thinking about bounded polytopes, even more specifically about 01-polytopes $P \subseteq \{0,1\}^n$. In that case a certificate for Conditions 1 and 2 can clearly be encoded in polynomial size and the problem is in NP. I am not sure about unbounded polyhedra.  
> **username_0**: Also in my case the polytopes are nonempty. Maybe the hardness of the decision problem "given $k$ affinely independent vectors in $P$, does there exist an additional vector that is affinely independent of the given $k$?" can be established by a reduction from feasibility of an ILP. Thanks for the pointer.  
> **username_1**: (i) How do you verify (in NP) Condition 2 for a given set of equalities even in the 0/1 case (given that you need to check whether all integer points in P satisfy those inequalities)?  The problem "Does a given ILP polytope have dimension at most $k$" seems co-NP hard, e.g. by reduction from UNSAT.  (ii)  By "an additional vector that..." do you mean "an additional vector in P that..."?  (iii)  Assuming so, the case k=0 is testing whether P is empty (NP-hard), and it seems likely that the cases k >= 1 can be reduced to from any given polytope just by adding some artificial variables...  
> **username_2**: Please [edit] your question to include all relevant information, such as that you are working over $\{0,1\}^n$.  People shouldn't have to read the comments to understand what you are asking.  

---

## 1 answers

### Answer by username_1 on 2021-11-12. Score: 2 | Accepted answer

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](https://math.stackexchange.com/questions/2564236/how-can-i-formulate-the-3-sat-problem-as-a-0-1-linear-integer-program). 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](https://cs.stackexchange.com/questions/77957/there-are-parsimonious-reductions-between-all-np-complete-problems-well-known-c) 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$...)


---

