1 Introduction

Convex polyhedra, i.e., the intersections of finitely many closed affine half-spaces in R^d, are important objects in various areas of mathematics and other disciplines. In particular, the compact ones among them (polytopes), which equivalently can be defined as the convex hulls of finitely many points in R^d, have been studied since ancient times (e.g., the platonic solids). Polytopes appear as building blocks of more complicated structures, e.g., in (combinatorial) topology, numerical mathematics, or computer aided design. Even in physics polytopes are relevant (e.g., in crystallography or string theory).

Probably the most important reason for the tremendous growth of interest in the theory of convex polyhedra in the second half of the 20^th century was the fact that linear programming (i.e., optimizing a linear function over the solutions of a system of linear inequalities) became a widespread tool to solve practical problems in industry (and military). Dantzig's Simplex Algorithm, developed in the late 40's, showed that geometric and combinatorial knowledge of polyhedra (as the domains of linear programming problems) is quite helpful for finding and analyzing solution procedures for linear programming problems.

Since the interest in the theory of convex polyhedra to a large extent comes from algorithmic problems, it is not surprising that many algorithmic questions on polyhedra arose in the past. But also inherently, convex polyhedra (in particular: polytopes) give rise to algorithmic questions, because they can be treated as finite objects by definition. This makes it possible to investigate (the smaller ones among) them by computer programs (like the polymake-system written by Gawrilow and Joswig, see [25] and [26][27]). Once chosen to exploit this possibility, one immediately finds oneself confronted with many algorithmic challenges.

This paper contains descriptions of 35 algorithmic problems about polyhedra. The goal is to collect for each problem the current knowledge about its computational complexity. Consequently, our treatment is focused on theoretical rather than on practical subjects. We would, however, like to mention that for many of the problems computer codes are available.

Our choice of problems to be included is definitely influenced by personal interest. We have not spent particular efforts to demonstrate for each problem why we consider it to be relevant. It may well be that the reader finds other problems at least as interesting as the ones we discuss. We would be very interested to learn about such problems. The collection of problem descriptions presented in this paper is intended to be maintained as a (hopefully growing) list at this site.

Almost all of the problems are questions about polytopes. In some cases the corresponding questions on general polyhedra are interesting as well. It can be tested in polynomial time whether a polyhedron specified by linear inequalities is bounded or not. This can be done by applying Gaussian elimination and solving one linear program.

Roughly, the problems can be divided into two types: problems for which the input are "geometrical" data and problems for which the input is "combinatorial" (see below). Actually, it turned out that it was rather convenient to group the problems we have selected into the five categories "Coordinate Descriptions" (Sect. 2), "Combinatorial Structure" (Sect. 3), "Isomorphism" (Sect. 4), "Optimization" (Sect. 5), and "Realizability" (Sect. 6). Since the boundary complex of a simplicial polytope is a simplicial complex, studying polytopes leads to questions that are concerned with more general (polyhedral) structures: simplicial complexes. Therefore, we have added a category "Beyond Polytopes" (Sect. 7), where a few problems concerned with general (abstract) simplicial complexes are collected that are closely related to similar problems on polytopes. We do not consider other related areas like oriented matroids.

The problem descriptions proceed along the following scheme. First input and output are specified. Then a summary of the knowledge on the theoretical complexity is given, e.g., it is stated that the complexity is unknown ("Open") or that the problem is NP-hard. This is done for the case where the dimension (usually of the input polytope) is part of the input as well as for the case of fixed dimension; often the (knowledge on the) complexity status differs for the two versions. After that, comments on the problems are given together with references. For each problem we tried to report on the current state of knowledge according to the literature. Unless stated otherwise, all results mentioned without citations are either considered to be "folklore" or "easy to prove." At the end related problems in this paper are listed.

For all notions in the theory of polytopes that we use without explanation we refer to Ziegler's book [66]. Similarly, for the concepts from the theory of computational complexity that play a role here we refer to Garey and Johnson's classical text [23]. Whenever we talk about polynomial reductions this refers to polynomial time Turing-reductions. For some of the problems the output can be exponentially large in the input. For these problems the interesting question is whether there is a polynomial total time algorithm, i.e., an algorithm whose running time can be bounded by a polynomial in the sizes of the input and the output (in contrast to a polynomial time algorithm whose running time would be bounded by a polynomial just in the input size). Note that the notion of "polynomial total time" only makes sense with respect to problems which explicitly require the output to be non-redundant.

A very fundamental result in the theory of convex polyhedra is due to Minkowski [46] and Weyl [65]. For the special case of polytopes (to which we restrict our attention from now on) it can be formulated as follows. Every polytope P⊂ R^d can be specified by an H- or by a V-description. Here, an H-description consists of a finite set of linear inequalities (defining closed affine half-spaces of R^d) such that P is the set of all simultaneous solutions to these inequalities. A V-description consists of a finite set of points in R^d whose convex hull is P. If any of the two descriptions is rational, then the other one can be chosen to be rational as well. Furthermore, in this case the numbers in the second description can be chosen such that their coding lengths depend only polynomially on the coding lengths of the numbers in the first description (see, e.g., Schrijver [57]). In our context, H- and V-descriptions are usually meant to be rational. By linear programming, each type of description can be made non-redundant in polynomial time (though it is unknown whether this is possible in strongly polynomial time, see Problem 25).

One of the basic properties of a polytope is its dimension. If the polytope is given by a V-description, then it can easily be determined by Gaussian elimination (which, carefully done, is a cubic algorithm; see, e.g., [57]). If the polyhedron is specified by an H-description, computing its dimension can be done by linear programming (actually, this is polynomial time equivalent to linear programming).

Furthermore, some of the problems may also be interesting in their polar formulations, i.e., with "the roles of H- and V-descriptions exchanged." Switching to the polar requires to have a relative interior point at hand, which is easy to obtain if a V-description is available, while it needs linear programming if only an H-description is specified.

We will especially be concerned with the combinatorial types of polytopes, i.e., with their face lattices (the sets of faces, ordered by inclusion). In particular, some problems will deal with the k-skeleton of a polytope, which is the set of its faces of dimensions less than or equal to k, or with its f-vector, i.e., the vector (f₀(P),f₁(P),…,f_d(P)), where f_i(P) is the number of i-dimensional faces (i-faces) of the d-dimensional polytope P (d-polytope). Talking of the face lattice L_P of a polytope P will always refer to the lattice as an abstract object, i.e., to any lattice that is isomorphic to the face lattice. In particular, the lattice does not contain any information on coordinates. Similarly, the vertex-facet incidences of P are given by any matrix (a_vf) with entries from {0,1}, whose rows and columns are indexed by the vertices and facets of P, respectively, such that a_vf=1 if and only if vertex v is contained in facet f. Note that the vertex-facet incidences of a polytope completely determine its face lattice.

A third important combinatorial structure associated with a polytope P is its (abstract) graph G_P, i.e., any graph that is isomorphic to the graph having the vertices of P as its nodes, where two of them are adjacent if and only if their convex hull is a (one-dimensional) face of P. For simple polytopes, the (abstract) graph determines the entire face lattice as well (see Problem 16). However, for general polytopes this is not true.

Throughout the paper, n refers to the number of vertices or points in the given V-description, respectively, depending on the context. Moreover, m refers to the number of facets or inequalities in the given H-description, respectively, and d refers to the dimension of the polytope or the ambient space, respectively.

Why are some symbols not displayed correctly?