Optimization Problems in the Polynomial-Time Hierarchy

Abstract

This talk surveys work on classifying the complexity and approximability of problems residing in the Polynomial-Time Hierarchy, above the first level. Along the way, we highlight some prominent natural problems that are believed – but not yet known – to be Σ^p₂-complete. We describe how strong inapproximability results for certain Σ^p₂ optimization problems can be obtained using dispersers to build error-correcting codes. Finally we adapt a learning algorithm to produce approximation algorithms for these problems.

Additional details