Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
2015 (English)In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, SPRINGER-VERLAG BERLIN , 2015, Vol. 9234, 357-368 p.Conference paper (Refereed)Text
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.
Lecture Notes in Computer Science, ISSN 0302-9743
Computer and Information Science
IdentifiersURN: 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
40th International Symposium on Mathematical Foundations of Computer Science (MFCS)