On the approximation complexity hierarchy.

Bordewich, Magnus

Abstract

This paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then there is a counting problem πA which neither has a fully polynomial randomised approximation scheme (FPRAS), nor is as hard to approximate as #SAT. This work is motivated by recent results showing that approximately counting H-colouring problems appears to fall into three complexity groups. Those problems which admit an FPRAS, those which are ‘AP-interreducible’ with #SAT and an intermediate class of problems all AP-interreducible with #BIS (counting independent sets in bipartite graphs). It has been asked whether this intermediate class in fact collapses into one of the former two classes, or whether it truly occupies some middle ground. Moreover, supposing it does occupy some middle ground, does it capture all the ground between? Our results reveal that there are counting problems whose approximation complexity lies between FPRASable and #SAT, under the assumption that NP≠RP. Indeed, there are infinitely many complexity levels between. Moreover we show that if #BIS is genuinely in the middle ground (neither having an FPRAS, nor as hard to approximate as #SAT), then there are problems that do not admit an FPRAS, are not equivalent in approximation complexity to #BIS and are not ‘AP-interreducible’ with #SAT, thus also occupy the middle ground. The proof is based upon Ladner’s original proof that there are classes between P and NP, and suffers the same drawback that the problems constructed are not natural. In particular our constructed problems are not H-colourings. The question of the approximation complexity of #BIS remains open.

Citation

Bordewich, M. (2011). On the approximation complexity hierarchy. In K. Jansen, & R. Solis-Oba (Eds.), 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool, UK, September 9-10, 2010. Revised Papers. https://doi.org/10.1007/978-3-642-18318-8_4

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010
• Publication Date: 2011
• Deposit Date: Aug 2, 2010
• Publisher: Springer Verlag
• Volume: 6534
• Series Title: Lecture Notes in Computer Science
• Book Title: 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool, UK, September 9-10, 2010. Revised Papers
• ISBN: 978-3-642-18317-1
• DOI: https://doi.org/10.1007/978-3-642-18318-8_4
• Public URL: https://durham-repository.worktribe.com/output/1159135