Near-threshold exponential resolution lower-bound conjecture for Term Coding

Let ΓL\Gamma\cup L be a single-sorted Term Coding problem, where Γ\Gamma is a set of term equations and LL is a set of non-equality constraints, over an nn-element alphabet. Define the set of solvable domain sizes

S={mN:ΓL has a solution for domain size m}.S=\{m\in\mathbb{N}:\Gamma\cup L\text{ has a solution for domain size }m\}.

Near-threshold resolution lower-bound conjecture. For an instance size nn with no solution, nSn\notin S, if

dist(n,S)=minmSnmlogO(1)(n),\operatorname{dist}(n,S)=\min_{m\in S}|n-m|\leq\log^{O(1)}(n),

then any resolution-based proof certifying non-existence of a solution for size nn via the corresponding SAT instance {SAT}Γ,L\{\mathrm{SAT}\}_{\Gamma,L} must have exponential size.

This conjecture concerns proof-complexity barriers near a solvability threshold. It is motivated by the stated dichotomy between polynomial-size proofs and failure in every infinite model, together with classical exponential resolution lower bounds; the source supplies no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Søren Riis, “Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies”, arXiv:2504.16265 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.