Generating all vertices of a polyhedron is hard.

Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich

Browse the full SODA paper archive.