On \({\mathbb{K}}^{\Delta}\) (Q1821691)

Let \({\mathbb{K}}\) be an unbounded convex polyhedral subset of \({\mathbb{R}}^ n\) represented by a system of linear constraints, and let \({\mathbb{K}}^{\Delta}\) be the convex hull of the set of extreme points of \({\mathbb{K}}\). We show that the combinatorial-facial structure of \({\mathbb{K}}\) does not uniquely determine the combinatorial-facial structure of \({\mathbb{K}}^{\Delta}\). We prove that the problem of checking whether two given extreme points of \({\mathbb{K}}\) are nonadjacent on \({\mathbb{K}}^{\Delta}\), is NP-complete in the strong sense. We show that the problem of deriving a linear constraint representation of \({\mathbb{K}}^{\Delta}\), leads to the question of checking whether the dimension of \({\mathbb{K}}^{\Delta}\) is the same as that of \({\mathbb{K}}\), and we prove that resolving this question is hard because it needs the solution of some NP-complete problems. Finally we provide a formula for the dimension of \({\mathbb{K}}^{\Delta}\), under a nondegeneracy assumption.