On the complexity of the clone membership problem
From MaRDI portal
Publication:2048213
DOI10.1007/s00224-020-10016-7OpenAlexW3124568226MaRDI QIDQ2048213
Publication date: 5 August 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.12211
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40)
Cites Work
- Unnamed Item
- Unnamed Item
- Clones with nullary operations.
- Generalized satisfiability for the description logic \(\mathcal{ALC}\)
- Using amplification to compute majority with small majority gates
- Root finding with threshold circuits
- A finite set of functions with an EXPTIME-complete composition problem
- On observational equivalence and algebraic specification
- On uniform circuit complexity
- On truth-table reducibility to SAT
- The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- The complexity of the descriptiveness of Boolean circuits over different sets of gates
- On uniformity within \(NC^ 1\)
- Efficient Multiparty Protocols via Log-Depth Threshold Formulae
- The complexity of reasoning for fragments of default logic
- The tractability of model checking for LTL
- Complexity Classifications for Propositional Abduction in Post's Framework
- Short monotone formulae for the majority function
- Bounded Query Classes
- GENCLO AND TERMEQUIV ARE EXPTIME-COMPLETE
- COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
- Satisfiability problems for propositional calculi
- Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
