A finite set of functions with an EXPTIME-complete composition problem

DOI10.1016/j.tcs.2008.06.057zbMath1152.68023OpenAlexW1981616529MaRDI QIDQ955009

Marcin Kozik

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.057

zbMATH Keywords

computational complexitycomposition of functionsclone membership problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (10)

Tractability in constraint satisfaction problems: a survey ⋮ The subpower membership problem for bands ⋮ Deciding the Existence of Minority Terms ⋮ On the number of finite algebraic structures ⋮ THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS ⋮ Finite Combinatory Logic with Intersection Types ⋮ ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM ⋮ Hardness results for the subpower membership problem ⋮ On the complexity of the clone membership problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a perfect strategy for nxn chess requires time exponential in n
• The subdirectly irreducible algebras in the variety generated by graph algebras
• The complexity of searching implicit graphs
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• N by N Checkers is Exptime Complete
• Composing Functions to Minimize Image Size
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• GO Is Polynomial-Space Hard
• Alternation
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS

This page was built for publication: A finite set of functions with an EXPTIME-complete composition problem