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

DOI10.1016/J.TCS.2008.06.057MaRDI QIDQ955009zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 3934404
• A problem of completeness of S-sets of deterministic functions
• scientific article; zbMATH DE number 6133272
• On total functions, existence theorems and computational complexity
• scientific article; zbMATH DE number 7300329
• On the complexity of certain completion problems
• On the complexity of finite sequences over a finite set
• Completeness problems in classes of computable named functions
• Composition limits and separating examples for some Boolean function complexity measures
• Complexity of term representations of finitary functions

Cites work

• scientific article; zbMATH DE number 3987347 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 598464 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• N by N Checkers is Exptime Complete
• Alternation
• COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
• COMPUTATIONAL COMPLEXITY OF THE FINITE ALGEBRA MEMBERSHIP PROBLEM FOR VARIETIES
• Composing Functions to Minimize Image Size
• Computing a perfect strategy for nxn chess requires time exponential in n
• GO Is Polynomial-Space Hard
• INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• The complexity of searching implicit graphs
• The subdirectly irreducible algebras in the variety generated by graph algebras

Cited in

(13)

• Tractability in constraint satisfaction problems: a survey
• A 2EXPTIME complete varietal membership problem
• A nonapproximability result for finite function generation
• Finite combinatory logic with intersection types
• Deciding the existence of minority terms
• On the number of finite algebraic structures
• The subpower membership problem for Mal'cev algebras
• The subpower membership problem for bands
• Hardness results for the subpower membership problem
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• Completeness criterion in class of exponential-polynomial functions
• The subpower membership problem for finite algebras with cube terms
• On the complexity of the clone membership problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955009)