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
Strong partial clones and the time complexity of SAT problems
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Technical University of Dresden, Germany.
Kvarnvagen 6, Sweden.
Normandie University, France.
2017 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 84, p. 52-78Article in journal (Refereed) Published
Abstract [en]

Improving exact exponential-time algorithms for NP-complete problems is an expanding research area. Unfortunately, general methods for comparing the complexity of such problems are sorely lacking. In this article we study the complexity of SAT(S) with reductions increasing the amount of variables by a constant (CV-reductions) or a constant factor (LV-reductions). Using clone theory we obtain a partial order amp;lt; on languages such that SAT(S) is CV-reducible to SAT(S) if S amp;lt; S. With this ordering we identify the computationally easiest NP-complete SAT(S) problem (SAT({R})), which is strictly easier than 1-in-3-SAT. We determine many other languages in amp;lt; and bound their complexity in relation to SAT({R}). Using LV-reductions we prove that the exponential-time hypothesis is false if and only if all SAT(S) problems are subexponential. This is extended to cover degree-bounded SAT(S) problems. Hence, using clone theory, we obtain a solid understanding of the complexity of SAT(S) with CV-and LV-reductions. (C) 2016 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
ACADEMIC PRESS INC ELSEVIER SCIENCE , 2017. Vol. 84, p. 52-78
Keyword [en]
Satisfiability problems; Computational complexity; Clone theory; Universal algebra; Subexponential time
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-133248DOI: 10.1016/j.jcss.2016.07.008ISI: 000388430000005OAI: oai:DiVA.org:liu-133248DiVA, id: diva2:1057615
Note

Funding Agencies|French National Research Agency (ANR) [ANR-10-BLAN-0210]; Swedish Research Council (VR) [2009-4431, 2012-3239, 2008-4675]; National Graduate School in Computer Science (CUGS), Sweden; DFG [622397]

Available from: 2016-12-19 Created: 2016-12-15 Last updated: 2018-01-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, PeterNordh, Gustav
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Journal of computer and system sciences (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 42 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