Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Klaus Jansen
Editor
Roberto Solis-Oba
Editor
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.
Bordewich, M. (2010, September). On the approximation complexity hierarchy. Presented at 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool
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 |
Print ISSN | 0302-9743 |
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 |
Quantifying the difference between phylogenetic diversity and diversity indices
(2024)
Journal Article
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Presentation / Conference Contribution
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search