liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Recognizing frozen variables in constraint satisfaction problems
Linköpings universitet, Tekniska högskolan. Linköpings universitet, Institutionen för datavetenskap, TCSLAB - Laboratoriet för teoretisk datalogi.
Departament of Computer Science, University of Durham, Durham, DH1 3LE, United Kingdom.
2004 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 329, nr 1-3, s. 93-113Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances. We show that the complexity of such problems is determined by certain algebraic properties of these relations. Under the assumption that NP ? coNP (and consequently PTIME ? NP), we characterize all tractable problems, and describe large classes of NP-complete, coNP-complete, and DP-complete problems. As an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2, and (2) when all unary relations are present. We also give a rough classification for domain size 3.© 2004 Elsevier B.V. All rights reserved.

Ort, förlag, år, upplaga, sidor
2004. Vol. 329, nr 1-3, s. 93-113
Nyckelord [en]
Computational complexity, Constraint satisfaction, Frozen variable, Polymorphism
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
URN: urn:nbn:se:liu:diva-45552DOI: 10.1016/j.tcs.2004.08.006OAI: oai:DiVA.org:liu-45552DiVA, id: diva2:266448
Tillgänglig från: 2009-10-11 Skapad: 2009-10-11 Senast uppdaterad: 2017-12-13

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Person

Jonsson, Peter

Sök vidare i DiVA

Av författaren/redaktören
Jonsson, Peter
Av organisationen
Tekniska högskolanTCSLAB - Laboratoriet för teoretisk datalogi
I samma tidskrift
Theoretical Computer Science
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 72 träffar
RefereraExporteraLänk till posten
Permanent länk

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