According to the [Wikipedia](https://en.wikipedia.org/wiki/Vertex_enumeration_problem) page on the issue, the vertex enumeration problem is NP-hard.


However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, Fukuda and Avis have published a library for it that works well for really large dimensional problems.


There's even a [question](https://mathoverflow.net/questions/203966/computionally-efficient-vertex-enumeration-for-convex-polytopes) on this site claiming it's pseudo-polynomial. So which one is it?



Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
As noted in the comments this is not a decision problem. But more than that typically we discuss P and NP in terms of polynomial time with respect to input size. In this problem, the input is the collection of inequalities/half-spaces. However, the output is the collection of vertices which can be exponential in the number of inequalities defining the polytope. So, no algorithm could output the vertices using only polynomial time in the input.


As a result, people often then talk about polynomial time in terms of the input and output size. I recommend the paper [Generating All Vertices of a Polyhedron Is Hard](https://doi.org/10.1007/s00454-008-9050-5) for information on the problem.


Lastly, note the algorithms discussed on Wikipedia talk about things like $O(ndv)$ where $n$ is the number of facets, $d$ is the dimension, and $v$ is the number of vertices. So, $n+v$ gives the combined size of the input and output, but there is also the $d$. This means you need to fix a dimension, talk about parameterized complexity, etc. If you try to apply the algorithm to any dimension you have an issue for large $d$ (theoretically, even if it seems to work on your examples).


