Completeness in the Polynomial-Time Hierarchy A Compendium ∗

Abstract

We present a Garey/Johnson-style list of problems known to be complete for the second and higher levels of the polynomial-time Hierarchy (polynomial hierarchy, or PH for short). We also include the best-known hardness of approximation results. The list will be updated as necessary. Updates The compendium currently lists more than 80 problems. Latest changes include: • added [GT26] SUCCINCT k-KING, • added [GT25] SUCCINCT k-DIAMETER, • added [GT4] SUCCINCT k-RADIUS at third level, • added [GT24] MINIMUM VERTEX COLORING DEFINING SET, • added [GT23] GRAPH SANDWICH PROBLEM FOR Π, • added [L24] MINIMUM 3SAT DEFINING SET,