Uniform Complexity Theory for Definable Graph Polynomials

Definitions and mathematical statement

Let $P$ denote a graph polynomial: an assignment $G\mapsto P(G;X_1,\ldots,X_r)$ invariant under graph isomorphism, with values in a polynomial ring. The source does not specify the permitted graphs, coefficient ring, number of indeterminates, or logical meaning of definability. These choices must be supplied before a particular class of such polynomials is fixed.

For a fixed polynomial assignment $P$ and a fixed admissible evaluation tuple $\mathbf a$, write \[ \operatorname{Eval}_{P,\mathbf a}:G\longmapsto P(G;\mathbf a). \] This denotes exact evaluation only after the input encoding, evaluation domain, and output representation have been specified. Write $n=|V(G)|$, and let $\operatorname{tw}(G)$ denote treewidth, understood as the minimum, over tree decompositions of $G$, of the largest bag size minus one, once the graph convention is fixed.

Source question. Can uniform theorems be established for large definable classes of graph polynomials that give all three of the following conclusions?

1. Almost-everywhere $\#\mathrm{P}$-hardness of evaluation.
2. Evaluation in time exponential in the number $n$ of vertices.
3. Fixed-parameter tractability of evaluation on graphs of bounded treewidth.

For the third conclusion, the usual interpretation, for fixed $P$ and $\mathbf a$, would be an evaluation algorithm with running time \[ f_{P,\mathbf a}\left(\operatorname{tw}(G)\right)\,L^c, \] where $L$ is the encoded input length, $f_{P,\mathbf a}$ is computable, and $c$ is independent of the treewidth parameter. This is an explanatory template, not a specification supplied by the source: whether $P$, the evaluation tuple, or a tree decomposition belongs to the input is unresolved.

Unresolved qualifications. The record does not identify a definable class or defining logic, the admissible evaluation points, the exceptional set intended by "almost everywhere," or the reductions intended by $\#\mathrm{P}$-hardness. It also does not specify the precise vertex-exponential bound, arithmetic versus bit complexity, or the meaning of uniformity across polynomials. Consequently, the record supports the research question above but does not determine a single fully quantified complexity conjecture. No universal hardness claim for all graph polynomials is asserted here.

Short English statement

The question asks whether broad, suitably defined classes of graph polynomials admit a common theory giving hardness at almost all evaluation points, evaluation algorithms exponential in the vertex count, and tractable evaluation parameterized by treewidth. The source leaves the classes, evaluation domains, exceptional points, computational model, and uniformity requirements unspecified, so a fully precise conjecture requires further source clarification.

Sources

• Local UnsolvedMath registry, permanent ID $30001378$, source problem code catalogue entry, title "Uniform Complexity Theory for Definable Graph Polynomials," in the supplied Oberwolfach Reports Open Problems collection. No individual proposer is supplied.
• Supplied source citation: Complexity Theory (2010), Oberwolfach Reports, pp. 2787--2850, DOI 10.4171/owr/2009/52. https://doi.org/10.4171/owr/2009/52. The record gives proposed year 2009 and describes these reports as documenting workshops and their open-problem discussions.
• Supplied literature source, labeled "original Oberwolfach report 4135": https://doi.org/10.4171/owr/2009/52.
• Supplied literature source, labeled "graph-polynomial complexity result": https://doi.org/10.3233/FI-2010-233.
• Supplied literature source, labeled "graph-polynomial complexity thesis": https://d-nb.info/1051091845/34.
• Supplied literature assessment dated exactly 2026-08-21: the record labels the problem open and describes Makowsky's difficult-point conjecture as remaining a general conjecture concerning broad classes of graph polynomials, with individual polynomials and subclasses supporting it without proving it. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment; the status and cited claims require independent verification. The record does not explicitly identify the displayed three-part question with a precise formulation of that conjecture.
• The supplied statement status is corrected_verified; its accompanying verification note reports only normalization of TeX-style punctuation without a change of mathematical content. It does not establish mathematical correctness or resolve the formulation issues above.