Skip to main content

Research Repository

Advanced Search

Constraint satisfaction, logic and forbidden patterns

Madelaine, F.R.; Stewart, I.A.

Constraint satisfaction, logic and forbidden patterns Thumbnail


Authors

F.R. Madelaine



Abstract

In the early nineties, Feder and Vardi attempted to find a large sub-class of NP which exhibits a dichotomy; that is, where every problem in the sub-class is either solvable in polynomial-time or NP-complete. Their studies resulted in a candidate class of problems, namely those definable in the logic MMSNP. Whilst it remains open as to whether MMSNP exhibits a dichotomy, for various reasons it remains a strong candidate. Feder and Vardi added to the significance of MMSNP by proving that although MMSNP strictly contains CSP, the class of constraint satisfaction problems, MMSNP and CSP are computationally equivalent. We introduce here a new class of combinatorial problems, the class of forbidden patterns problems FPP, and characterize MMSNP as the finite unions of problems from FPP. We use our characterization to detail exactly those problems that are in MMSNP but not in CSP. Furthermore, given a problem in MMSNP, we are able to decide whether the problem is in CSP or not (this whole process is effective). If the problem is in CSP then we can construct a template for this problem, otherwise for any given candidate for the role of template, we can build a counter-example (again, this process is effective).

Citation

Madelaine, F., & Stewart, I. (2007). Constraint satisfaction, logic and forbidden patterns. SIAM Journal on Computing, 37(1), 132-163. https://doi.org/10.1137/050634840

Journal Article Type Article
Publication Date Apr 1, 2007
Deposit Date Oct 7, 2008
Publicly Available Date Mar 29, 2024
Journal SIAM Journal on Computing
Print ISSN 0097-5397
Electronic ISSN 1095-7111
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 37
Issue 1
Pages 132-163
DOI https://doi.org/10.1137/050634840
Keywords Finite model theory, Constraint satisfaction, Existential monadic second-order logic.
Publisher URL http://www.dur.ac.uk/i.a.stewart/Papers/FPPvsCSP.pdf

Files

Published Journal Article (319 Kb)
PDF

Copyright Statement
© Society for Industrial and Applied Mathematics





You might also like



Downloadable Citations