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
Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2015 (English)In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9234, 357-368 p.Conference paper, Published paper (Refereed)
Resource type
Text
Abstract [en]

The monotone constraint satisfaction problem (MCSP) is the problem of, given an existentially quantified positive formula, decide whether this formula has a model. This problem is a natural generalization of the constraint satisfaction problem, which can be seen as the problem of determining whether a conjunctive formula has a model. In this paper we study the worst-case time complexity, measured with respect to the number of variables, n, of the MCSP problem parameterized by a constraint language Gamma (MCSP(Gamma)). We prove that the complexity of the NP-complete MCSP(G) problems on a given finite domain D falls into exactly vertical bar D vertical bar-1 cases and ranges from O(2(n)) to O(vertical bar D vertical bar(n)). We give strong lower bounds and prove that MCSP(G), for any constraint language Gamma over any finite domain, is solvable in O(vertical bar Dvertical bar n) time, where D- is the domain of the core of Gamma, but not solvable in O(vertical bar Dvertical bar(delta n)) time for any delta < 1, unless the strong exponential-time hypothesis fails. Hence, we obtain a complete understanding of the worst-case time complexity of MCSP(Gamma) for constraint languages over arbitrary finite domains.

Place, publisher, year, edition, pages
SPRINGER-VERLAG BERLIN , 2015. Vol. 9234, 357-368 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-126283DOI: 10.1007/978-3-662-48057-1_28ISI: 000371025600033ISBN: 978-3-662-48057-1; 978-3-662-48056-4 (print)OAI: oai:DiVA.org:liu-126283DiVA: diva2:913369
Conference
40th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Available from: 2016-03-21 Created: 2016-03-21 Last updated: 2016-03-21

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lagerkvist, Victor
By organisation
Software and SystemsFaculty of Science & Engineering
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 8 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