PaperlayerView exact revision on arXiv

Source-linked AI summary

A dichotomy theorem for nonuniform CSPs

Andrei A. Bulatov

arXiv:1703.03021v2cs.CC

TL;DR

The paper addresses the Feder–Vardi Dichotomy Conjecture for nonuniform CSPs. Using an algebraic approach, it proves the dichotomy for finite constraint languages and develops a uniform algorithm whose behavior depends only on the associated algebra.

  • Problem

    The paper addresses the open Dichotomy Conjecture concerning the complexity of nonuniform CSPs.

  • Method

    The paper uses the algebraic structure of CSPs, including quasi-centralizers and related technical lemmas, to construct a uniform solution algorithm.

  • Results

    For every finite constraint language Γ over a finite set, CSP(Γ) is either solvable in polynomial time or NP-complete.

  • Takeaways & Limitations

    The solution algorithm can depend only on the finite idempotent algebra A rather than on the individual constraint language.

  • Takeaways & Limitations

    The reduction of strategies uses the condition MAX(P) ∩Center(P) = ∅.

Abstract

from arXiv · show

In this paper we prove the Dichotomy Conjecture on the complexity of nonuniform constraint satisfaction problems posed by Feder and Vardi.

1 Introduction

Nonuniform CSPs restrict allowed relations to a constraint language, and the paper confirms the Feder–Vardi dichotomy for every finite language over a finite set. It also gives a uniform algorithmic formulation whose solution algorithm depends only on the associated finite idempotent algebra.

  • Background: A nonuniform CSP, CSP(Γ), asks whether constraints drawn from a fixed relation set Γ can be simultaneously satisfied.Constraint languages provide a framework connected to homomorphism problems and MMSNP.
  • Background: The Feder–Vardi Dichotomy Conjecture asks whether every finite constraint language over a finite set yields a polynomial-time or NP-complete problem.The conjecture followed earlier dichotomy results for languages over two-element domains.
  • Main result: The paper proves that for every finite constraint language Γ over a finite set, CSP(Γ) is either solvable in polynomial time or NP-complete.This confirms the Dichotomy Conjecture for arbitrary finite languages over finite sets.
  • Main result: The hardness direction was already known; the main achievement is a polynomial-time algorithm for languages satisfying the algebraic tractability condition.The algorithm is first established for languages containing all singleton constant relations, which implies the general dichotomy.
  • Algebraic formulation: For a finite idempotent algebra satisfying the conjecture’s conditions, the paper gives a uniform solution algorithm for CSP(A).The stronger formulation states that the solution algorithm depends only on the algebra A, even when constituent CSP(Γ) problems may otherwise use different algorithms.
  • Paper organization: The paper’s first part presents the main algorithmic ideas self-containedly, while the second develops the algebraic approach and technical proofs.The paper introduces CSP terminology, algebraic preliminaries, and key ingredients before the more involved technical sections.

2 Introduction to CSP

The paper formulates nonuniform CSPs through constraint languages and universal algebras, then characterizes polynomial-time solvability using algebraic operations and structural properties. It proves the dichotomy for finite idempotent algebras and relates it to algorithms for CSP instances.

  • CSP formulation: A nonuniform CSP(Γ) asks whether variables can be assigned values satisfying constraints whose relations come from Γ.Instances consist of variables and explicitly represented constraint relations, and solutions are mappings from variables to the domain.
  • Algebraic framework: Polymorphisms are operations preserving every relation in a constraint language and provide the main algebraic framework for studying CSP complexity.The approach connects constraint languages with universal algebras of polymorphisms and supports reductions between CSPs.
  • Algebraic framework: For an algebra A, CSP(A) comprises CSPs whose relations are invariant under the operations of A, with tractability understood either separately or uniformly.The paper studies whether one polynomial-time algorithm can solve all problems in this algebraically defined class.
  • Dichotomy criterion: For finite idempotent A, polynomial-time solvability is equivalent to A having a weak near-unanimity term operation.Idempotence also makes constant relations invariant and reduces the general conjecture to the idempotent setting.
  • Dichotomy criterion: If every algebra in HS(A) has a nontrivial term operation, CSP(A) is polynomial-time solvable; otherwise, it is NP-complete.Here HS(A) contains quotient algebras of subalgebras, and projections are excluded from the nontrivial operations.
  • Algorithms: Two major algorithmic approaches are local propagation for bounded-width CSPs and a few-subpowers method that yields polynomial-time solvability under specified algebraic conditions.The few-subpowers result applies when an idempotent algebra has no semilattice edges and has few subpowers.

3 Solving CSPs

This section introduces congruence separation and quasi-centralizers as algebraic tools for decomposing CSP instances, then uses them in a polynomial-time algorithm based on block-minimality and recursive reductions.

  • 3.1 Congruence separation and centralizers: The algorithm’s two key ingredients are congruence separation and quasi-centralizers.Quasi-centralizers resemble centralizers from commutator theory, but their precise relationship is left unclear.
  • 3.1 Congruence separation and centralizers: Polynomial operations define separation between prime congruence intervals, while non-separability can be treated as an equivalence relation under suitable conditions.The same notion extends to prime intervals in different coordinates of a relation.
  • 3.1 Congruence separation and centralizers: Large quasi-centralizers impose aligned block structure that can lift solutions between corresponding congruence blocks.For semilattice-linked blocks, the induced mapping supports lifting a solution from one block to another.
  • 3.2 The algorithm: Non-separable intervals yield a decomposition of a CSP subinstance into instances whose variable domains are corresponding quasi-centralizer blocks.Every solution of the original subinstance solves one decomposed instance.
  • 3.2 The algorithm: Subdirect irreducibility, block-minimality, and quotient transformations organize the algorithm’s instances and enable efficient domain reduction.Subdirect irreducibility can be enforced in polynomial time, while block-minimality uses smaller domains or quotient algebras.
  • 3.2 The algorithm: If a structured instance satisfies the stated conditions, it has a solution; recursive calls reduce non-semilattice-free domain sizes and therefore run in polynomial time.The solution guarantee is stated for subdirectly irreducible, (2,3)-minimal, block-minimal instances with MAX(P) ∩Center(P) = ∅.

Technicalities

The paper’s second part develops the algebraic machinery and technical proofs underlying the algorithm, especially separating factors and strategy-tightening arguments.

  • Technicalities: The second part extends results on colored graphs and relational structures before developing separation methods in congruence lattices.These developments support the algebraic analysis used later in the algorithm.
  • Technicalities: The algorithm first applies few-subpowers methods when domains lack semilattice edges, and otherwise usually establishes block-minimality.The remaining problematic case motivates additional strategy-based arguments.
  • Technicalities: For block-minimal instances, strategies are tightened to solve quotient problems and reduce semilattice edges.The tightening process repeatedly reduces domains to classes of maximal congruences, with separate Abelian and non-Abelian cases.

4 Preliminaries

These preliminaries define CSP instances, algebraic notation, congruences, polynomials, and minimal sets, together with the tame-congruence facts used later.

  • 4 Preliminaries: The notation fixes projections, subdirect products, subalgebras, congruences, polynomials, and quotient algebras for the algebraic treatment.Congruences induce well-defined quotient algebras on their blocks.
  • 4 Preliminaries: A CSP asks whether assignments satisfy all specified relations; a nonuniform CSP restricts those relations to a constraint language Γ.Instances use variables, constraint scopes, and explicitly represented relation tuples.
  • 4 Preliminaries: CSP instances support restrictions, solution sets, domain reductions, quotient transformations, and standard forms of local consistency.1-minimal, (2,3)-consistent, and (2,3)-minimal instances can be obtained in polynomial time by constraint propagation.
  • 4 Preliminaries: An (α, β)-minimal set is an inclusion-minimal unary-polynomial image that witnesses β not being contained in α.Minimal sets are polynomially isomorphic, and idempotent unary polynomials can map the algebra onto them.
  • 4 Preliminaries: Tame congruence theory classifies prime intervals through minimal-set structure, while perspective intervals share type and minimal sets.Under the paper’s tractability assumptions, type 1 does not occur.

5 Separating congruences

This section develops separating congruences and polynomials as tools for analyzing prime intervals, then derives collapsing polynomials and type constraints used in the algebraic approach to CSPs.

  • 5.1 Separation: Separating congruences distinguish prime intervals when a unary polynomial preserves one lower congruence while failing to preserve the other.The same definition is extended from a single algebra to prime intervals in coordinate positions of a subdirect product.
  • 5.2 Separation: Separation in an algebra is equivalent to separation in its binary equality relation viewed as a subdirect product.The equivalence follows because a polynomial acts identically on both projections of the equality relation.
  • 5.2 Separation: Lemma 43 shows that a separating polynomial can be chosen idempotent with image a minimal set for the separated prime interval.This connects separation directly to the minimal-set machinery used later in the construction.
  • 5.3 Collapsing polynomials: Prime intervals that cannot be separated from each other admit polynomials collapsing all other intervals while preserving the selected group.The construction repeatedly composes unary polynomials, strictly shrinking image size until every unwanted pair is collapsed.
  • 5.4 Separation and minimal sets: For mutually non-separable prime intervals, Lemma 49 bounds link congruences by the lower congruences whenever the interval type is not 2.Corollary 50 further establishes that mutually non-separable intervals have the same type.

6 Centralizers and decomposition of CSPs

This section introduces the quasi-centralizer of a congruence interval and studies how it governs algebraic structure and decomposition relations in CSP instances.

  • 6.1 Quasi-Centralizer: The quasi-centralizer ζ(α, β) records when changing one parameter leaves the condition f_a(β) ⊆ α unchanged for every term operation.It is later shown to be the greatest relation satisfying the corresponding compatibility condition.
  • 6.1 Quasi-Centralizer: ζ(α, β) is an equivalence relation and is preserved by term operations, so it is a congruence of the algebra.The proof establishes reflexivity, symmetry, transitivity, and compatibility with term operations.
  • 6.1 Quasi-Centralizer: When ζ(α, β) contains β, the interval has type 2 and semilattice-linked β-blocks admit injective maps between their α-quotients.The maps preserve the thin-edge direction and send each source element below its image.
  • 6.1 Quasi-Centralizer: For any thin edge between β-blocks in the same quasi-centralizer block, an explicitly defined polynomial gives an injective mapping between the corresponding α-quotients.The polynomial is selected according to whether the edge is semilattice, majority, or affine.
  • 6.2 Decomposition of CSPs: Non-separable prime intervals in two factors force the coordinate positions to be quasi-centralizer-aligned in their subdirect product.Alignment means congruence-related pairs in one coordinate correspond exactly to congruence-related pairs in the other.

7 The Congruence Lemma

This section develops closure properties and the Congruence Lemma for polynomially closed subalgebras and related subdirect products. The lemma controls link congruences and yields graph-of-a-mapping and rectangularity consequences under additional conditions.

  • Closure properties: The section introduces polynomially closed and as-closed relations, establishing that these properties persist under intersections, pp-definitions, and suitable congruence quotients.These closure results support later transformations of relations and subalgebras.
  • The Congruence Lemma: The Congruence Lemma shows that, under additional conditions, a restricted relation becomes the graph of a mapping whose kernel is the corresponding restricted congruence.This identifies the relation’s structure when one coordinate’s link congruence is equality.
  • Auxiliary structure: The first auxiliary lemmas analyze binary relations containing nonseparable type-2 prime intervals, showing that their structure is uniform on blocks of link congruences.The analysis focuses on chained subdirect products and selected congruence blocks.
  • Consequences: When the relevant link congruence is nontrivial on a block, it contains the associated quotient congruence and propagates relations across the entire block modulo the lower congruence.The resulting rectangularity statement is expressed as {c} × B/γ ⊆ R/γ.
  • Scope of the conditions: The section notes that one of its two sufficient conditions need not contain u-maximal elements, so neither condition strictly generalizes the other.This limits direct comparison between the two cases.

8 Chaining

This section strengthens chaining to strong chaining and proves that the strengthened property is preserved under specified relation transformations. The proof uses polynomial witnesses, as-components, link congruences, and majority operations.

  • Definition and purpose: The section introduces strong chaining as a property stronger than chaining and uses its preservation under transformations in later β-strategy proofs.Lemma 65 is the principal preservation result.
  • Witnesses: Strong-chaining conditions require polynomial witnesses connecting related elements through minimal sets and prescribed coordinate blocks.The witnesses are constrained by separation and congruence data in conditions such as (Q2s).
  • Case analysis: The proof reduces the main transformation argument to linked and nonlinked cases for a projected relation Q.In the nonlinked case, the Congruence Lemma makes Q the graph of a mapping and forces one link congruence to be equality.
  • Extension to maximal elements: The transformation argument concludes by extending connectivity from selected elements to u-maximal elements while maintaining the required block-preserving conditions.The construction proceeds in two steps, first building chains and then adjusting the witnessing polynomials.

9 Strategies and solutions

This section presents the algorithmic scheme for solving CSP(A): preprocess instances, handle semilattice-free domains, enforce block-minimality, recursively reduce smaller instances, and apply the main structural theorem. The resulting algorithm is correct and polynomial-time.

  • Preprocessing: The solution scheme begins with preprocessing and transforms instances into subdirectly irreducible, (2,3)-minimal, and block-minimal forms.Every CSP instance can first be reduced to an equivalent subdirectly irreducible one.
  • Block-minimality: A (2,3)-minimal instance can be transformed into an equivalent block-minimal instance by solving a quadratic number of strictly smaller CSPs.The transformation repeatedly tightens constraints when the block-minimality tests fail.
  • Semilattice-free domains: If all domains are semilattice free, the instance is solved in polynomial time using the few subpowers algorithm.This is the first case of the grand scheme.
  • Recursive reductions: When centralizer conditions permit, the algorithm solves a quotient instance, flags values without compatible solutions, tightens the instance, and recursively calls itself on strictly smaller instances.The procedure includes quotienting, global 1-minimality checks, and reductions based on Theorem 69.
  • Existence theorem: Theorem 68 guarantees a solution for subdirectly irreducible, (2,3)-minimal, block-minimal instances with MAX(P) ∩ Center(P) = ∅.This theorem is the central existence step in the nontrivial-centralizer case.
  • Correctness and complexity: Algorithm SolveCSP correctly solves every instance from CSP(A) in polynomial time, with running time bounded by O(n^3k).Here k is the maximal size of an algebra in A; polynomiality follows from linear restart and recursion bounds.

10 Proof of Theorem 68

The remaining part of the paper proves Theorem 68.

  • The section is devoted to proving Theorem 68.
  • The proof occurs in the remaining part of the paper.
  • Theorem 68 is the result established in this section.

10.1 Tightening affine factors

The affine tightening strategy selects a type-2 congruence interval, restricts domains and relations, and proves the transformed relations preserve the required strategy conditions.

  • Case selection: The case assumes α ≺ βv with typ(α, βv) = 2, so the relevant quotient Bv/α is a module.The construction selects an α-block B and uses its module structure to define the tightening.
  • Transformation: The transformed relations R′ are defined by retaining tuples that extend to compatible solutions under the selected domain restrictions and congruence blocks.The construction also defines induced congruences τU on projections and distinguishes full from maximal congruences.
  • Induced congruences: The induced congruences τU are chosen through the Congruence Lemma and satisfy restriction, fullness, or maximality conditions across variable subsets.These congruences connect projected solution relations with the selected affine factor.
  • Relation comparison: The key relation comparison shows that maximal elements of the transformed relation are obtained from the original maximal elements intersected with the relevant block.It also establishes a product inclusion in the quotient relation, which is used to verify later strategy properties.
  • Verified conditions: R′ satisfies polynomial closure and forms a nonempty (2,3)-strategy, while also satisfying conditions (S2) and (S3).The cited lemmas establish these properties separately, including extension of compatible projected tuples.

10.2 Tightening non-affine factors

The non-affine tightening restricts domains in two stages, constructs auxiliary binary relations, and proves that the resulting relations satisfy all strategy conditions.

  • 10.2 Tightening non-affine factors: For typ(α, βv) ≠ 2, tightening first restricts Bv to an as-component and then restricts it to one α-block.The first restriction may fail (S5) and (S6), which the second restriction is designed to restore.
  • Step 1: The construction obtains a restricted instance P′ and then establishes (2,3)-minimality together with additional compatibility conditions.The restricted domains include the generated subalgebra bD for v and the original domains for other variables.
  • Step 2: The auxiliary relations Qx and Qxy retain as-maximal values compatible with the selected α-block and form subdirect products of the corresponding unary relations.Their properties support extension arguments across triples and constraints.
  • Extension properties: For every pair relation Qxy, compatible as-maximal tuples can be extended through a third variable, and projected compatible tuples can be extended to full constraint tuples.An induction on the size of variable sets supplies the required extensions.
  • Conclusion: The resulting collection R′′ satisfies all the conditions of a strategy.The construction preserves as-maximal Q-compatible tuples through subsequent minimality operations.

Index

The index lists terminology and notation used throughout the paper, including algebraic types, congruences, CSP constructions, and strategy-related objects.

  • Terminology: The index includes CSP and strategy terms such as globally minimal instance, minimal instance, tightening, P-compatible, T-compatible, and operation preserving a relation.It also records witnesses, projections, polynomial operations, and named constructions.
  • Terminology: The index covers congruence and relation concepts including link congruences, link tolerances, prime intervals, separated intervals, and strongly chained relations.These entries identify recurring algebraic tools in the paper.
  • Terminology: The terminology index includes algebraic structures and types such as modules, monoliths, majority, semilattice, and thin edges.It also lists maximal components, maximal elements, and related connectivity notions.

Notation

The notation index records symbols for algebras, instances, relations, projections, compatibility sets, strategies, and maximal-element operators.

  • Instances and solutions: Core instance notation includes P = (V, C), SP, PW, P′, and PR.These symbols refer to CSP instances and their solution or restricted forms.
  • Relations and projections: Relation and projection notation includes PR, P x, P xy, prIR, Qx, Qxy, and QA.The index groups symbols used for projected relations and auxiliary compatibility relations.
  • Auxiliary notation: Additional notation includes W′, size(P), umax(A), and WP(µY).The index also records symbols for strategy domains and maximal-element constructions.
Loading 1703.03021v2…