Gritzmann, Klee, and Larman [28] 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 [28]). Gritzmann et al. also prove that the case where j = d is strongly NP-hard if P is given by a V-description. Packer [51] 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 [28].

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 [51] 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. [51].