Near-threshold exponential resolution lower-bound conjecture for Term Coding
Near-threshold exponential resolution lower-bound conjecture for Term Coding
Let be a single-sorted Term Coding problem, where is a set of term equations and is a set of non-equality constraints, over an -element alphabet. Define the set of solvable domain sizes
Near-threshold resolution lower-bound conjecture. For an instance size with no solution, , if
then any resolution-based proof certifying non-existence of a solution for size via the corresponding SAT instance 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.