On the complexity of the clone membership problem
type: Item
instance of: scholarly article
title: On the complexity of the clone membership problem
author: Emil Jeřábek
published in: Theory of Computing Systems
publication date: 2021-08-05T00:00:00Z
full work available at URL: https://arxiv.org/abs/1909.12211
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 08A40
zbMATH DE Number: 7379118
zbMATH Keywords: clone membership
zbMATH Keywords: Boolean functions
zbMATH Keywords: polynomial hierarchy
zbMATH Keywords: threshold functions
MaRDI profile type: Publication
OpenAlex ID: W3124568226
cites work: On uniformity within \(NC^ 1\)
cites work: The tractability of model checking for LTL
cites work: Clones with nullary operations.
cites work: Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras
cites work: COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE
cites work: The complexity of reasoning for fragments of default logic
cites work: The complexity of the descriptiveness of Boolean circuits over different sets of gates
cites work: On truth-table reducibility to SAT
cites work: Efficient Multiparty Protocols via Log-Depth Threshold Formulae
cites work: Complexity Classifications for Propositional Abduction in Post's Framework
cites work: Using amplification to compute majority with small majority gates
cites work: Root finding with threshold circuits
cites work: A finite set of functions with an EXPTIME-complete composition problem
cites work: Function Algebras on Finite Sets
cites work: Satisfiability problems for propositional calculi
cites work: A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
cites work: GENCLO AND TERMEQUIV ARE EXPTIME-COMPLETE
cites work: Generalized satisfiability for the description logic \(\mathcal{ALC}\)
cites work: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
cites work: On uniform circuit complexity
cites work: On observational equivalence and algebraic specification
cites work: The complexity of satisfiability problems
cites work: Q3739181
cites work: Short monotone formulae for the majority function
cites work: The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis
cites work: Bounded Query Classes
cites work: Q3762226
DOI: 10.1007/S00224-020-10016-7
description: scientific article; zbMATH DE number 7379118