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

DOI10.1016/j.tcs.2008.06.057zbMath1152.68023MaRDI 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 complexity; composition of functions; clone membership problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

08A40: Operations and polynomials in algebraic structures, primal algebras

Related Items

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

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