×

Weak bases of Boolean co-clones. (English) Zbl 1296.68080

Summary: Universal algebra has proven to be a useful tool in the study of constraint satisfaction problems (CSP) since the complexity, up to logspace reductions, is determined by the clone of the constraint language. But two CSPs corresponding to the same clone may still differ substantially with respect to worst-case time complexity, which makes clones ill-suited when comparing running times of CSP problems. In this article we instead consider an algebra where each clone splits into an interval of strong partial clones such that a strong partial clone corresponds to the CSPs that are solvable within the same \(O(c^n)\) bound. We investigate these intervals and give relational descriptions, weak bases, of the largest elements. They have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones has a simpler structure than the lattice of partial clones.

MSC:

68Q25 Analysis of algorithms and problem complexity
08A40 Operations and polynomials in algebraic structures, primal algebras
08A70 Applications of universal algebra in computer science

References:

[1] Alekseev, V. B.; Voronenko, A. A., On some closed classes in partial two-valued logic, Discrete Appl. Math., 4, 5, 401-419 (1994) · Zbl 0818.06013
[2] Allender, E.; Bauland, M.; Immerman, N.; Schnoor, H.; Vollmer, H., The complexity of satisfiability problems: refining Schaefer’s theorem, J. Comput. Syst. Sci., 75, 4, 245-254 (June 2009) · Zbl 1161.68487
[3] Böhler, E.; Creignou, N.; Reith, S.; Vollmer, H., Playing with Boolean blocks, part I: Post’s lattice with applications to complexity theory, ACM SIGACT-Newsl., 34, 4, 38-52 (2003)
[4] Böhler, E.; Schnoor, H.; Reith, S.; Vollmer, H., Bases for Boolean co-clones, Inf. Process. Lett., 96, 2, 59-66 (2005) · Zbl 1184.68351
[5] Creignou, N.; Kolaitis, P.; Zanuttini, B., Structure identification of Boolean relations and plain bases for co-clones, J. Comput. Syst. Sci., 74, 7, 1103-1115 (November 2008) · Zbl 1152.68020
[6] Geiger, D., Closed systems of functions and predicates, Pac. J. Math., 27, 1, 95-100 (1968) · Zbl 0186.02502
[7] Jeavons, P., On the algebraic structure of combinatorial problems, Theor. Comput. Sci., 200, 185-204 (1998) · Zbl 0915.68074
[8] Jonsson, P.; Lagerkvist, V.; Nordh, G.; Zanuttini, B., Complexity of SAT problems, clone theory and the exponential time hypothesis, (Proc. SODA-2013 (2013)), 1264-1277 · Zbl 1423.68212
[9] Lagerkvist, V., Weak bases (2014) · Zbl 1296.68080
[10] Lau, D., Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory, Springer Monogr. Math. (2006), Springer-Verlag: Springer-Verlag New York, Inc., Secaucus, NJ, USA · Zbl 1105.08001
[11] Post, E., The two-valued iterative systems of mathematical logic, Ann. Math. Stud., 5, 1-122 (1941) · Zbl 0063.06326
[12] Romov, B. A., The algebras of partial functions and their invariants, Cybernetics, 17, 2, 157-167 (1981) · Zbl 0466.03026
[13] Schnoor, H.; Schnoor, I., Partial polymorphisms and constraint satisfaction problems, (Creignou, N.; Kolaitis, P. G.; Vollmer, H., Complexity of Constraints. Complexity of Constraints, Lect. Notes Comput. Sci., vol. 5250 (2008), Springer: Springer Berlin, Heidelberg), 229-254 · Zbl 1171.68502
[14] Schnoor, I., The weak base method for constraint satisfaction (2008), Gottfried Wilhelm Leibniz Universität: Gottfried Wilhelm Leibniz Universität Hannover, Germany, PhD thesis
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.