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

Direct link
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 (Refereed)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-4OAI: 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
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

Altmetric score

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link