On the Complexity of the Clone Membership Problem

1. Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC¹. J. Comput. Syst. Sci. 41(3), 274–306 (1990)

   Article  Google Scholar 

2. Bauland, M., Mundhenk, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The tractability of model checking for LTL: the good, the bad, and the ugly fragments. ACM Trans. Comput. Logic 12(2). Article no. 13, 28 pp. (2011)

3. Behrisch, M.: Clones with nullary operations. Electron. Notes Theor. Comput. Sci. 303, 3–35 (2014)

   Article  MathSciNet  Google Scholar 

4. Bergman, C., Slutzki, G.: Complexity of some problems concerning varieties and quasi-varieties of algebras. SIAM J. Comput. 30(2), 359–382 (2000)

   Article  MathSciNet  Google Scholar 

5. Bergman, C., Juedes, D., Slutzki, G.: Computational complexity of term-equivalence. Int. J. Algebra Comput. 9(1), 113–128 (1999)

   Article  MathSciNet  Google Scholar 

6. Beyersdorff, O., Meier, A., Thomas, M., Vollmer, H.: The complexity of reasoning for fragments of default logic. J. Logic Comput. 22(3), 587–604 (2012)

   Article  MathSciNet  Google Scholar 

7. Böhler, E., Schnoor, H.: The complexity of the descriptiveness of Boolean circuits over different sets of gates. Theory Comput. Syst. 41(4), 753–777 (2007)

   Article  MathSciNet  Google Scholar 

8. Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, pp. 319–330 (2017)

9. Buss, S.R.: The Boolean formula value problem is in ALOGTIME. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 123–131 (1987)

10. Buss, S.R., Hay, L.: On truth-table reducibility to SAT. Inf. Computat. 91(1), 86–102 (1991)

    Article  MathSciNet  Google Scholar 

11. Cohen, G., Damgård, I.B., Ishai, Y., Kölker, J., Miltersen, P.B., Raz, R., Rothblum, R.D.: Efficient multiparty protocols via log-depth threshold formulae. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology—CRYPTO 2013. Proceedings, Part II, Lecture Notes in Computer Science, vol. 8043, pp. 185–202. Springer (2013). Full version available at http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmajority_mpc-1.pdf

12. Creignou, N., Schmidt, J., Thomas, M.: Complexity classifications for propositional abduction in Post’s framework. J. Logic Comput. 22(5), 1145–1170 (2012)

    Article  MathSciNet  Google Scholar 

13. Gupta, A., Mahajan, S.: Using amplification to compute majority with small majority gates. Comput. Complex. 6(1), 46–63 (1996)

    Article  MathSciNet  Google Scholar 

14. Jeřábek, E.: Root finding with threshold circuits. Theor. Comput. Sci. 462, 59–69 (2012)

    Article  MathSciNet  Google Scholar 

15. Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 254–266 (1977)

16. Kozik, M.: A finite set of functions with an EXPTIME-complete composition problem. Theor. Comput. Sci. 407, 330–341 (2008)

    Article  MathSciNet  Google Scholar 

17. Ladner, R.E.: The circuit value problem is log space complete for \(\mathcal P\). ACM SIGACT News 7(1), 18–20 (1975)

    Article  Google Scholar 

18. Lau, D.: Function algebras on finite sets: a basic course on many-valued logic and clone theory. Springer, New York (2006)

    MATH  Google Scholar 

19. Lewis, H.R.: Satisfiability problems for propositional calculi. Math. Syst. Theory 13, 45–53 (1979)

    Article  MathSciNet  Google Scholar 

20. Lukasiewicz, T., Malizia, E.: A novel characterization of the complexity class \({\Theta }_{k}^{\mathrm {P}}\) based on counting and comparison. Theor. Comput. Sci. 694, 21–33 (2017)

    Article  Google Scholar 

21. Mašulović, D.: GenClo and TermEquiv are EXPTIME-complete. Int. J. Algebra Comput. 18(5), 901–909 (2008)

    Article  MathSciNet  Google Scholar 

22. Meier, A., Schneider, T.: Generalized satisfiability for the description logic \(\mathcal {{ALC}}\). Theor. Comput. Sci. 505, 55–73 (2013)

    Article  MathSciNet  Google Scholar 

23. Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. No. 5 in Annals of Mathematics Studies. Princeton University Press, Princeton (1941)

    Google Scholar 

24. Reith, S.: Generalized satisfiability problems. Ph.D. thesis, Julius-Maximilians-Universität, Würzburg (2001)

25. Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22(3), 365–383 (1981)

    Article  MathSciNet  Google Scholar 

26. Sannella, D., Tarlecki, A.: On observational equivalence and algebraic specification. J. Comput. Syst. Sci. 34(2–3), 150–178 (1987)

    Article  MathSciNet  Google Scholar 

27. Schaefer, T. J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216–226 (1978)

28. Szendrei, Á.: Clones in universal algebra, Séminaire de mathématiques supérieurs, vol. 99. Université de Montréal (1986)

29. Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363–366 (1984)

    Article  MathSciNet  Google Scholar 

30. Vollmer, H.: The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis. Theory Comput. Syst. 44(1), 82–90 (2009)

    Article  MathSciNet  Google Scholar 

31. Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19(5), 833–846 (1990)

    Article  MathSciNet  Google Scholar 

32. Wegener, I.: The Complexity of Boolean Functions. Teubner, Stuttgart (1987)

    MATH  Google Scholar 

33. Zhuk, D.: A proof of CSP dichotomy conjecture. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science, pp. 331–342 (2017)

Download references