Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem

DOI10.1016/S0885-064X(02)00027-4zbMath1012.68185OpenAlexW2054620325MaRDI QIDQ1869963

Steve Seif, Csaba Szabó

Publication date: 4 May 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0885-064x(02)00027-4

zbMATH Keywords

complexitysemigroupgraph homomorphismconstraint satisfaction

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Complexity issues of checking identities in finite monoids ⋮ Equivalence and equation solvability problems for the alternating group \(\mathbf A_4\). ⋮ Identity checking problem for transformation monoids ⋮ MONOIDS AND COMPUTATIONS ⋮ THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS

Cites Work

• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Absolute retracts of bipartite graphs
• List homomorphisms and circular arc graphs
• The equivalence problem for finite rings
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

This page was built for publication: Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem