liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Constructing NP-intermediate problems by blowing holes with parameters of various properties
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 581, 67-82 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
Computational complexity; NP-intermediate problems; Constraint satisfaction problems; Abduction problems
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-118236DOI: 10.1016/j.tcs.2015.03.009ISI: 000353608700005OAI: oai:DiVA.org:liu-118236DiVA: diva2:813544
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]; National Graduate School in Computer Science (CUGS) [12.02]

Available from: 2015-05-22 Created: 2015-05-22 Last updated: 2017-12-04

Open Access in DiVA

fulltext(495 kB)34 downloads
File information
File name FULLTEXT01.pdfFile size 495 kBChecksum SHA-512
9e09368b265df1a2819a9b4c41c71f0ab3e6f2a37ca9f387114868f3493e8ad0ae768b6d1a774f1bb801785fee4c8682a44e9fe6c18a88231e538fa6b422030a
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterLagerkvist, VictorNordh, Gustav

Search in DiVA

By author/editor
Jonsson, PeterLagerkvist, VictorNordh, Gustav
By organisation
Software and SystemsFaculty of Science & EngineeringThe Institute of Technology
In the same journal
Theoretical Computer Science
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 34 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 82 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf