The complexity of the Chinese Remainder Theorem

The Chinese Remainder Theorem for the integers asserts that every system of congruence equations is solvable provided that an obvious necessary condition holds. This statement can be naturally generalized to arbitrary algebraic structures within the framework of Universal Algebra. A tuple of congruences of an algebra is called a Chinese Remainder tuple if every compatible system involving them is solvable. In this paper, we study the computational complexity of deciding whether a given tuple of congruences of a finite algebra is a Chinese Remainder tuple. We show that this problem, denoted by [Formula: see text], is coNP-complete. Moreover, we establish a Cook reduction from [Formula: see text] to CSP. When the input algebra is known to belong to a fixed congruence permutable variety or generates a congruence meet-semidistributive variety, this reduction enables the application of existing efficient CSP algorithms to solve the corresponding promise versions of [Formula: see text]. In particular, this implies that [Formula: see text] is solvable in polynomial time for a broad range of well-studied classes, including any variety interpreting the variety of groups or the variety of semilattices. Finally, we address the restriction of [Formula: see text] to an arbitrary variety generated by a two-element algebra. Here we establish a dichotomy by showing that for each of these varieties the problem is either coNP-complete or tractable.