|Input:||Polytope P of dimension d, positive integer 1 £ j £ d|
|Output:||A j-simplex contained in (containing) P of largest (smallest) volume|
|Status (fixed dim.):||Polynomial time|
Among the j-simplices of largest volume contained in P, there
is one whose vertices are vertices of P. Hence, one can restrict
attention to (j+1)-subsets of the vertices of P.
Gritzmann, Klee, and Larman  prove NP-hardness of the problem to find a largest j-simplex contained in a d-polytope P, where P is either given by a V-description or by an H-description and j is part of the input. The corresponding decision problems to decide whether there exists a j-simplex whose squared volume is larger than a given K are in NP(see ). Gritzmann et al. also prove that the case where j = d is strongly NP-hard if P is given by a V-description. Packer  additionally proves that this case is NP-hard if P is given by an H-description.
If j is fixed and P is given by a V-description, the problem is solvable in polynomial time. However, if P is given by an H-description the problem is NP-hard for each fixed 1 £ j £ d, see .
If d is fixed, the problem to find a largest j-simplex is solvable in polynomial time: if P is given by an V-description we can enumerate all j-simplices in polynomial time and if P is given by an H-description we can first enumerate all vertices and then all j-simplices.
Packer  also proves that the corresponding problem to find a d-simplex of smallest volume containing P is NP-hard, where P is either given by V- or H-description. It is unknown whether the decision problems for the squared volume of j-simplices containing P are in NP, cf. .