From complexity to algebra and back:: digraph classes, collapsibility and the PGP

Catarina Carvalho; Florent Madelaine; Barnaby Martin

doi:10.1109/LICS.2015.50

From complexity to algebra and back: digraph classes, collapsibility and the PGP

Catarina Carvalho, Florent Madelaine, Barnaby Martin

Centre for Computer Science and Informatics Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Citations (Scopus)

88 Downloads (Pure)

Abstract

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.

Original language	English
Title of host publication	Proceedings of the 2015 30th Annual ACM / IEEE Symposium on logic in Computer Science (LICS)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	462-474
Number of pages	13
ISBN (Print)	1043-6871
DOIs	https://doi.org/10.1109/LICS.2015.50
Publication status	Published - 3 Aug 2015
Event	30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) - Kyoto, Japan Duration: 6 Jul 2015 → 10 Jul 2015

Conference

Conference	30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015)
Country/Territory	Japan
City	Kyoto
Period	6/07/15 → 10/07/15

Keywords

algebra
complexity theory
cloning
polynomials
electronic mail
concrete

Access to Document

10.1109/LICS.2015.50

907109
© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 831 KB

Cite this

@inproceedings{98d3bbb0d7954ddfacdaa0e5b80a00ef,

title = "From complexity to algebra and back:: digraph classes, collapsibility and the PGP",

abstract = "Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even {"}gap{"}, theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.",

keywords = "algebra, complexity theory, cloning, polynomials, electronic mail, concrete",

author = "Catarina Carvalho and Florent Madelaine and Barnaby Martin",

note = "This is the accepted version of the following article: C. Carvalho, M. Florent, & M. Barnaby, “Fom complexity to algebra and back: digraph classes, collapsibility, and the PGP”, published in Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 6-10 July 2015, IEEE Xplore Digital Library, August 2015. The final, published version is available online via doi: 10.1109/LICS.2015.50 {\textcopyright} 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.; 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) ; Conference date: 06-07-2015 Through 10-07-2015",

year = "2015",

month = aug,

day = "3",

doi = "10.1109/LICS.2015.50",

language = "English",

isbn = "1043-6871",

pages = "462--474",

booktitle = "Proceedings of the 2015 30th Annual ACM / IEEE Symposium on logic in Computer Science (LICS)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

}

Carvalho, C, Madelaine, F & Martin, B 2015, From complexity to algebra and back: digraph classes, collapsibility and the PGP. in Proceedings of the 2015 30th Annual ACM / IEEE Symposium on logic in Computer Science (LICS). Institute of Electrical and Electronics Engineers (IEEE), pp. 462-474, 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), Kyoto, Japan, 6/07/15. https://doi.org/10.1109/LICS.2015.50

From complexity to algebra and back: digraph classes, collapsibility and the PGP. / Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby.
Proceedings of the 2015 30th Annual ACM / IEEE Symposium on logic in Computer Science (LICS). Institute of Electrical and Electronics Engineers (IEEE), 2015. p. 462-474.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - From complexity to algebra and back:

T2 - 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015)

AU - Carvalho, Catarina

AU - Madelaine, Florent

AU - Martin, Barnaby

N1 - This is the accepted version of the following article: C. Carvalho, M. Florent, & M. Barnaby, “Fom complexity to algebra and back: digraph classes, collapsibility, and the PGP”, published in Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 6-10 July 2015, IEEE Xplore Digital Library, August 2015. The final, published version is available online via doi: 10.1109/LICS.2015.50 © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2015/8/3

Y1 - 2015/8/3

N2 - Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.

AB - Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.

KW - algebra

KW - complexity theory

KW - cloning

KW - polynomials

KW - electronic mail

KW - concrete

U2 - 10.1109/LICS.2015.50

DO - 10.1109/LICS.2015.50

M3 - Conference contribution

SN - 1043-6871

SP - 462

EP - 474

BT - Proceedings of the 2015 30th Annual ACM / IEEE Symposium on logic in Computer Science (LICS)

PB - Institute of Electrical and Electronics Engineers (IEEE)

Y2 - 6 July 2015 through 10 July 2015

ER -