On the Complexity of CSP-based Ideal
Membership Problems
Andrei A. Bulatov
Simon Fraser University
Joint work with Akbar Rafiey

CiE, 2023

Overview Polynomials and ideals
 Polynomials in complexity and algorithms
 Constraint Satisfaction Problem
 CSPs and ideals
 Tractability
 Search and Applications

2/44

Polynomials and Ideals

3/44

Rings and IdealsLetbe a field and [ , … ,over . Here = ℝ or ℂ.

] the ring of polynomials

An ideal ℐ ⊆ [ , … , ] is a set of polynomials such that for
any , ∈ ℐ and ℎ ∈ [ , … , ] we have+ , ℎ ⋅ ∈ ℐ.

4/44

Ideal Membership Problem
Ideal Membership Problem (IMP).
Input: An ideal ℐ ⊆ [ , … , ] and a polynomial .
Question: Does belong to ℐ?

An ideal is given by its generators, ℐ = 〈 , … , 〉Hilbert’s Basis Theorem:
Every ideal of,…,has finitely many generators.
5/44

Solving IMP
Ideal Membership Problem (IMP).
Input: Polynomials , , … ,∈ [ , … , ].
Question: Do there exist ℎ , … , ℎ ∈ [ , … , ] such that= ℎ ⋅ + ⋯+ ℎ ⋅ ?
Search: Find ℎ , … , ℎ ∈ [ , … , ] such that= ℎ ⋅ + ⋯+ ℎ ⋅Polynomials ℎ , … , ℎ∈ 〈 ,…, 〉are called a Nullstellensatz proof that
6/44

Solving IMP 2
The IMP cannot be solved simply by dividing

by,…,.

The usual way of solving the IMP is to construct a Gröbner
basis of the ideal.
Dividing by polynomials from a Gröbner basis is much better
behaved.

7/44

Polynomials in Complexity and Algorithms

8/44

IMP in Computer Science
Combinatorial problems as polynomial ideals
2-Coloring
This graph is 2-colourable iff the polynomials
1 − , (1 − ), (1 − ),domain polynomials
instance+ − 1, + − 1, + − 1
have a common zero

9/44

Nullstellensatz
Nullstellensatz.
Let ℐ ⊆ [ , … , ] be a (radical) ideal and ⊆the setof all zeroes of polynomials from ℐ. Then every ∈ [ , … , ]that vanishes at every point of belongs to ℐ.
The graph from the previous slide has no 2-coloring iff 1 belongs
to the ideal generated by those polynomials:
1 = (−4)−1 + 2 −1+−1 −+ −1 +[ +− 1]
10/44

IMP as a Proof SystemIMP may provide a witness that an instance has no solution:- encode your problem through polynomials , … ,- check if 1 belongs to 〈 , … , 〉- or find ℎ , … , ℎ such that 1 = ℎ ⋅ + … + ℎ ⋅Nullstellensatz proof system
Proof complexity: What is the `size’ of the smallest proof?

11/44

IMP and Approximation
We may want to show that a problem not only doesn’t have asolution, it doesn’t have anything close to a solution
Formally, construct a `loss function’ that is 0 on a solution, andprove some lower bound for it
Or we may want to optimize some function on solutions
1 − , (1 − ), (1 − ),+ − 1, + − 1, + − 1

In our example= + −1 "+ + −1 "+ + −1 "To show that ≥ 1, represent − 1 as a sum of squares plus a
12/44
polynomial from the ideal

IMP and SoS
Let $ = {& , … , &ℓ } be a set of polynomials.
Polynomial has a Sum-of-Squares (SoS) proof of nonnegativity,from $ if there are polynomials , … , ) and ℎ , … , ℎℓ suchthat=*)+,"+ +*ℓ+,ℎ+ &+13/44

Constraint Satisfaction Problem

14/44

Constraint Satisfaction Problem
Definition:
Instance: (V;A;C) where♦ V is a finite set of variables♦ A is a set of values

CSP(Γ)♦ C is a set of constraints - . , … , -/ ./where each -+ belongs to Γ, a constraint language

Objective: whether there is ℎ: 1 → 3 such that,for any 4, -+ (ℎ .+ ) is true

15/44

Examples: SAT
3-SAT = CSP( 56789: ):( X ∨ Y ∨ Z ) ∧ ( X ∨ U ∨ V ) ∧ (U ∨ T ∨ Z )16/44

Examples: k-Coloringk-Coloring:
Instance: A graph= = (1, >)≠≠≠≠≠≠≠

CSP(≠)≠≠≠≠≠

Objective: Is it k-colorable?
H-Coloring : Edge relation of a graph ; rather than ≠17/44

Examples: Linear Equations
Linear Equations:
Instance: A system of linear equations
25+ ? + 1.5 B"−2 D−3 ?
−2 G+2 B

Objective: Is it consistent?

==⋮
=30
1

CSP(5HII )(affinerelations)

18/44

Invariants and Polymorphisms
Definition Relation R is invariant w.r.t. an n-ary operation f(or f is a polymorphism of R) if, for any JK , … , JK ∈ - thetuple obtained by applying f coordinate-wise belongs to RPol(Γ) denotes the set of all polymorphisms of relations from ΓTheorem (Jeavons et al., 1998)
If Pol(Γ) ⊆ Pol(∆), thenCSP(∆) is polytime reducible to CSP(Γ)
19/44

Polymorphisms: Examples
Consider - ∈ ΓMNN , it is the set of solutions of a system
3⋅ ⃗ =P
Then operation, , = − + is a polymorphism of Indeed, take ⃗, ⃗, ⃗ ∈ -, that is, 3 ⋅ ⃗ = 3 ⋅ ⃗ = 3 ⋅ ⃗ = PThen3⋅ ⃗− ⃗+ ⃗ =3⋅ ⃗−3⋅ ⃗+3⋅ ⃗=P−P+P =P

20/44

Good Polymorphisms
A semilattice operation is a binary operation ⋅ satisfying theequations: x ⋅ x = x, x ⋅ y = y ⋅ x, x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z(Horn SAT)
A majority operation is a ternary operation ℎ that satisfies theequations
g(x,x,y) = g(x,y,x) = g(y,x,x) = x(2-SAT)
A Maltsev operation is a ternary operation ℎ that satisfies theequations
h(x,x,y) = h(y,x,x) = y(systems of linear equations)
21/44

Schaefer’s Theorem
Schaefer’s Dichotomy Theorem (Schaefer 1978)
For a Boolean constraint language Γ, CSP(Γ) is poly time iff
one of the following operations is a polymorphism of Γ constant 0 (constant 1) operation
 disjunction ∨ (conjunction ∧) majority operation ∧ ∨ ∧ ∨ ( ∧ ) affine (Mal’tsev) operation − +Otherwise it is NP-complete.
22/44

General Dichotomy Theorem

CSP Dichotomy Theorem (Bulatov, Zhuk, 2017)
For a constraint language Γ on a finite set, CSP(Γ) is polytime iff a weak near-unanimity operation is a polymorphism of Γ.
Otherwise it is NP-complete.
V( , … , ) ) is WNU if
V ,…, , = V,…, ,= ⋯ = V( , … , , )23/44

IMP and CSP

24/44

IMP from CSP
Let W be an instance of XY$(Γ) where Γ is a constraint
language over Z = {0, … , [ − 1}.
Let { , … , } be the set of variables of W
For every constraint X = 〈+\ , … , +], -〉 introduce apolynomial ^ ∈ ℝ[ +\ , … , +] ] whose zeroes are exactly thetuples of ℐ W is the ideal of ℝ , … ,generated by ^ , for all
constraints X and domain polynomials _ + , 4 ≤ a.

25/44

IMP from CSP 2bc$(Γ):
Input: an instance W of XY$(Γ) with variables { , … ,polynomial ∈ ℝ[ , … , ]Question: ∈ ℐ(W)?
Also, find a proof that ∈ ℐ(W)} and abc$d (Γ) is the subproblem of bc$(Γ) in which the degree ofis bounded by e
26/44

IMP from CSP 3ℐ(W) is always radical, so Nullstellensatz applies
bc$(Γ):
Input: an instance W of XY$(Γ) with variables { , … ,polynomial ∈ ℝ[ , … , ]Question: is every solution of W a zero of ?

} and aCorollarybc$ Γ ∈ fgh$
27/44

Research QuestionsQuestion 1: For which Γ a Groebner basis of ℐ(W) can be
efficiently constructed for every W?

Question 2: For which Γ there is a `small’ Nullstellensatz proofof ∈ ℐ(W) for every , W?
Question 3:time?

For which Γ the problem bc$d (Γ) is polynomial
28/44

Boolean IMPTheorem (Mastrolilli’19, Mastrolilli,Bharati’20)
Let Γ be a constraint language over {0,1}. Then
If Γ has a majority, semilattice or affine ( − + )polymorphism then bc$d Γ is polytime for any eOtherwise bc$" (Γ) is coNP-completeTractable cases are through GB

29/44

Tractability

30/44

Polytime IMPTheorem.
(1) bc$d (semilattice) is polytime for every e.
(2) bc$d dual discriminator is polytime for every e(3) bc$d (ℤw ), & prime, is polytime for every e(4) bc$d (x) is polytime for every e, x is an Abelian group31/44

Abelian Groups CaseConsider bcZ(ℤw )The CSP instance is a system of linear equations
yJJ+ ⋯+J⋮+⋯+ J=P=P

The polynomial encoding is exponentially long
Change the domain

32/44

Abelian Groups Case 2
Step 1. Solve the system
y=f=f+ ⋯+ f⋮z + ⋯+ fzzz+P+P

Step 2. Replace Z = 0,1, … , [ − 1 with [th roots of unity {|} is a primitive root|−1
domain polynomials€••‚\~•+−}z …

€•ƒinstance

It is a GB

33/44

Abelian Groups Case 3
Step 3. Convert the input polynomial
Let „: {| → Z, „(}+ ) → 4
It is represented by a polynomial
Convert ( , … , ) to … = („,…,„)

Lemma.
… belongs to the ideal generated by the polynomials from
Step 2 if and only if belongs to the ideal corresponding to theoriginal instance.
34/44

Search and Applications

35/44

The Search Problem
The reductions shown above allow for a solution of the decision
problem. However, substitutions completely mess up proofs andGB
We show a reduction of the search problem to the decision
problem. It involves constructing a GB using the decision problem

36/44Extended IMP†bc$(Γ):Input: an instance W of XY$(Γ) with variables { , … ,sequence of polynomials , … ,∈ ℝ[ , … , ]Question: Do there exist ‡ , … , ‡ ∈ ℝ such that‡+⋯+ ‡∈ ℐ(W)?

} and a37/44

Extended IMP 2
All the algebraic properties of the bc$ remain true for the†bc$.

Also, all the tractable cases of the bc$ remain tractable for the†bc$.

38/44

Extended IMP and the Search Problem
Theorem.
If †bc$(Γ) can be solved in polynomial time then for any
instance W of XY$(Γ), a degree e truncated Gröbner basis canalso be constructed in polynomial time.
Proof idea.
Enumerate all the monomials of degree at most e.
For each of them use the †bc$ to decide if a GB should containa polynomial with such a leading monomial and find it.
39/44

†bc$ and Bit Complexity
Recall SOS proofs:=*)+,"+ +*ℓ+,ℎ+ &+use †bc$ to decide if − ∑)+, +"belongs to the ideal generated by the &+40/44

IMP and SoS 2--

If it is known that an instance has an SoS proof of low degree,
it can be found through an SDP program of polynomial size.
Then the SDP program can be solved by the ellipsoid method
Low degree SoS proofs can be found. Such proof systems arecalled automatizable. Used in an attempt to refute the UGCAccident: It turns out low degree is not enough, also needsmall coefficients (O’Donnell’17)
Can almost be avoided in the majority of interesting cases,
provided the IMP part is polytime (Raghavendra’17)
41/44

†bc$ and Bit Complexity 2Raghavendra and Weitz suggested 3 conditions that guaranteethat an SOS proof has low bit complexity.
The approach above eliminates 2 of them for problems XY$(Γ)

42/44

Open Questions-More polytime problems
Connection to the standard CSP techniques (consistency?)
Low degree restrictions. What do they correspond to in CSP?

43/44

Thank You!

44/44