{'fraction_non_alphanumeric': 0.01834862385321101, 'fraction_numerical': 0.005897771952817824, 'mean_word_length': 4.9186046511627906, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Complexity of Some Polyhedral Enumeration Problems

In this thesis we consider the problem of converting the halfspace representation of a polytope to its vertex representation — the Vertex Enumeration problem — and various other basic and closely related computational problems about polytopes. The problem of converting the vertex representation to halfspace representation — the Convex Hull problem — is equivalent to vertex enumeration. In chapter 3 we prove that enumerating the vertices of an unbounded Hpolyhedron P is NP -hard even if P has only 0/1 vertices. This strengthens a previous result of Khachiyan et. al. [KBB+06]. In chapters 4 to 6 we prove that many other operations on polytopes like computing the Minkowski sum, intersection, projection, etc. are NP -hard for many representations and equivalent to vertex enumeration in many others. In chapter 7 we prove various hardness results about a cone covering problem where one wants to check whether a given set of polyhedral cones cover another given set. We prove that in general this is an NP -complete problem and includes important problems like vertex enumeration and hypergraph transversal as special cases. Finally, in chapter 8 we relate the complexity of vertex enumeration to graph isomorphism by proving that a certain graph isomorphism hard problem is graph isomorphism easy if and only if vertex enumeration is graph isomorphism easy. We also answer a question of Kaibel and Schwartz about the complexity of checking self-duality of a polytope.