Towards weak bases of minimal relational clones on all finite sets

Description

Weak bases of relational clones have been used in the past as a theoretical tool to establish more fine-grained complexity analyses of computational problems, see, e.g., [6,1,5,8,3]. For the Boolean case weak bases have been determined by Lagerkvist in [7], see also the discussion in [2]. The quest for weak bases on sets of larger size was begun in [4] with a study of weak bases for maximal clones, resulting in a complete description for all maximal clones on a three-element set. We shall report on extending this work to all maximal clones on any finite set. [1] M. Behrisch, M. Hermann, S. Mengel, G. Salzer. Minimal distance of propositional models, Theory Comput. Syst. 63(6) 1131–1184(2019). DOI 10.1007/s00224-018-9896-8 [2] M. Behrisch. Weak bases for Boolean relational clones revisited, in IEEE 52nd ISMVL 2022, Dallas, TX, May 18–20, 2022, 68–73(2022). DOI 10.1109/ISMVL52857.2022.00017 [3] M. Behrisch. On weak bases for Boolean relational clones and reductions for computational problems, To appear in Journal of Applied Logics [4] M. Behrisch. Weak bases for maximal clones, in IEEE 53rd ISMVL 2023, Matsue, Japan, May 22–24, 2023, 128–133(2023). DOI 10.1109/ISMVL57333.2023.00034 [5] M. Couceiro, L. Haddad, V. Lagerkvist. Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: a survey, in IEEE 49th ISMVL 2019, Fredericton, Canada, May 21–23, 2019, 170–175(2019). DOI 10.1109/ISMVL.2019.00037 [6] P. Jonsson, V. Lagerkvist, G. Nordh, B. Zanuttini. Strong partial clones and the time complexity of SAT problems, J. Comput. System Sci. 84 52–78(2017). DOI 10.1016/j.jcss.2016.07.008 [7] V. Lagerkvist. Weak bases of Boolean co-clones, Inform. Process. Lett. 114(9) 462–468(2014). DOI 10.1016/j.ipl.2014.03.011 [8] V. Lagerkvist, B. Roy. Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem, J. Comput. System Sci. 117 23–39(2021). DOI 10.1016/j.jcss.2020.10.004

Period	03 Sept 2023
Event title	Summer School on General Algebra and Ordered Sets 2023
Event type	Conference
Location	SlovakiaShow on map