Constructing NP-intermediate problems by blowing holes with parameters of various properties
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 581, 67-82 p.Article in journal (Refereed) Published
The search for natural NP-intermediate problems is one of the holy grails within computational complexity. Ladners original diagonalization technique for generating NP-intermediate problems, blowing holes, has a serious shortcoming: it creates problems with a highly artificial structure by arbitrarily removing certain problem instances. In this article we limit this problem by generalizing Ladners method to use parameters with various characteristics. This allows one to define more fine-grained parameters, resulting in NP-intermediate problems where we only blow holes in a controlled subset of the problem. We begin by fully characterizing the problems that admit NP-intermediate subproblems for a broad and natural class of parameterizations, and extend the result further such that structural CSP restrictions based on parameters that are hard to compute (such as tree-width) are covered, thereby generalizing a result by Grohe. For studying certain classes of problems, including CSPs parameterized by constraint languages, we consider more powerful parameterizations. First, we identify a new method for obtaining constraint languages Gamma such that CSP(Gamma) are NP-intermediate. The sets Gamma can have very different properties compared to previous constructions (by, for instance, Bodirsky and Grohe) and provides insights into the algebraic approach for studying the complexity of infinite-domain CSPs. Second, we prove that the propositional abduction problem parameterized by constraint languages admits NP-intermediate problems. This settles an open question posed by Nordh and Zanuttini. (C) 2015 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
Elsevier , 2015. Vol. 581, 67-82 p.
Computational complexity; NP-intermediate problems; Constraint satisfaction problems; Abduction problems
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-118236DOI: 10.1016/j.tcs.2015.03.009ISI: 000353608700005OAI: oai:DiVA.org:liu-118236DiVA: diva2:813544
Funding Agencies|Swedish Research Council (VR) [621-2012-3239]; National Graduate School in Computer Science (CUGS) [12.02]2015-05-222015-05-222015-05-27