VERTEX ENUMERATION is strongly polynomially equivalent to Problem 3 (see Avis, Bremner, and Seidel [1]). Since Problem 2 is strongly polynomially equivalent to Problem 3 as well, VERTEX ENUMERATION is also strongly polynomially equivalent to Problem 2.

For fixed d, Chazelle [12] found an O(m^⌊d/2⌋ ) polynomial time algorithm, which is optimal by the Upper Bound Theorem of McMullen [43]. There exist algorithms which are faster than Chazelle's algorithm for small n, e.g., an O(m log n + (m n)^{1-1/(⌊d/2⌋ +1)} polylog m) algorithm of Chan [9].

For general d, the reverse search method of Avis and Fukuda [2] solves the problem for simple polyhedra in polynomial total time, using working space (without space for output) bounded polynomially in the input size. An algorithm of Bremner, Fukuda, and Marzetta [8] solves the problem for simplicial polytopes. Note that these algorithms need a vertex of P to start from. Provan [54] gives a polynomial total time algorithm for enumerating the vertices of polyhedra arising from networks.

There are many more algorithms known for this problem - none of them is a polynomial total time algorithm for general polytopes. See the overview article of Seidel [59]. Most of these algorithms can be generalized to directly work for unbounded polyhedra, too.