Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
Department of Computer and Information Science, Linköping University, Sweden.
Department of Computer and Information Science, Linköping University, Sweden.
Jönköping University, Tekniska Högskolan, JTH, Avdelningen för datateknik och informatik.
Linköping, Sweden.
2021 (engelsk)Inngår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 892, s. 1-24, artikkel-id 106161Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized [Formula presented] problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that [Formula presented] can be solved at least as fast as any other NP-hard [Formula presented] problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways.

sted, utgiver, år, opplag, sider
Elsevier, 2021. Vol. 892, s. 1-24, artikkel-id 106161
Emneord [en]
Constraint satisfaction problems, Fine-grained complexity, Universal algebra, Computational complexity, Polynomial approximation, Constraint-satisfaction problems, Exponential time hypothesis, Fine grained, Logical reasoning, Optimisations, Reasoning problems, Relative complexity, Time complexity
HSV kategori
Identifikatorer
URN: urn:nbn:se:hj:diva-54769DOI: 10.1016/j.tcs.2021.09.006ISI: 000710586100001Scopus ID: 2-s2.0-85114918264Lokal ID: HOA;;768129OAI: oai:DiVA.org:hj-54769DiVA, id: diva2:1598174
Forskningsfinansiär
Swedish Research Council, 2017-04112, 2019-03690Tilgjengelig fra: 2021-09-28 Laget: 2021-09-28 Sist oppdatert: 2021-11-15bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Schmidt, Johannes

Søk i DiVA

Av forfatter/redaktør
Schmidt, Johannes
Av organisasjonen
I samme tidsskrift
Theoretical Computer Science

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 129 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf