gpt 6 astra ultra attempt on CS-376

Submodular partition: a valid two-part reduction and a failed repeated-cut algorithm

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A set function $f:2^V\to\mathbb R$ is submodular if $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$ for all $S,T\subseteq V$. A $k$-partition is a collection of pairwise disjoint nonempty sets $V_1,\ldots,V_k$ with union $V$. Its cost is $\sum_{i=1}^kf(V_i)$. The integer $k$ is fixed while $|V|$ grows.

Statement recorded in the supplied source.

For fixed $k$, what is the computational complexity of minimizing the sum of a submodular function over a partition into $k$ nonempty parts? [S2]

Scope qualification.

Complexity depends on the representation of $f$; a value-oracle model and an explicit finite representation are different problems. The supplied question does not impose monotonicity, symmetry, or a particular representation, so none is assumed here.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Determine the complexity of dividing a ground set into a fixed number of nonempty parts of minimum total submodular cost.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004898 (OWR-8415356-002). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Combinatorial Optimization, Oberwolfach Reports 53/2021, primary report PDF https://ems.press/content/serial-article-files/46931. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

For fixed $k$, what is the computational complexity of minimizing the sum of a submodular function over a partition into $k$ nonempty parts?

The route tested

The source permits general submodular functions, not only graph cuts, and fixes the number of nonempty parts. We test whether a sequence of optimal two-part cuts suffices. The two-part objective has a useful exact submodular form, but the proposed repeated-cut extension fails on an explicit five-vertex graph.

The two-part objective remains submodular.

Define $g(S)=f(S)+f(V\setminus S)$. Applying submodularity to $A,B$ and then to their complements gives \[ g(A)+g(B)\ge g(A\cap B)+g(A\cup B). \] Indeed the unions and intersections of the complements are the complements of $A\cap B$ and $A\cup B$, respectively. Also $g(S)=g(V\setminus S)$. Its value is exactly the cost of the corresponding two-part partition when $S$ is nonempty and proper. Thus a two-part instance can be treated by minimizing this symmetric function subject to that exclusion. For example one may enumerate ordered distinct terminals $a,b$ and minimize on sets containing $a$ but not $b$; every nontrivial set occurs in one such subproblem. We do not here reprove or implement a polynomial submodular-minimization oracle. This identity alone is not an algorithm for the general fixed-$k$ case.

An exact counterexample to repeated optimal splitting.

Take vertices $0,1,2,3,4$. Vertices $1,2,3,4$ form a complete graph with all six edge weights equal to six. The only edge incident to $0$ is $01$, of weight fifteen. Let $f(S)$ be the total weight of edges with exactly one endpoint in $S$. This is nonnegative and symmetric. It is submodular: adding a vertex $v$ to a set changes its contribution from each incident edge $vu$ by $+w_{vu}$ if $u$ is outside and by $-w_{vu}$ if $u$ is inside. Enlarging the set can only decrease this marginal. Summing marginals while adding $A\setminus B$ one element at a time proves the submodular inequality for any $A,B$.

Every cut that splits the four clique vertices crosses at least three clique edges, so has weight at least eighteen. The cut $\{0\}$ has weight fifteen and is the unique minimum cut up to complementation. Thus an algorithm that first takes an optimal two-way split must isolate $0$. Splitting the remaining clique optimally then cuts eighteen more weight, producing a three-part partition with total inter-part edge weight thirty-three and partition cost sixty-six, since every crossing edge is counted once from each endpoint's part.

The true minimum three-part cost is sixty. To see this exactly, the total graph edge weight is $36+15=51$. For a partition into three nonempty parts, the part sizes are either $3,1,1$ or $2,2,1$. In the first case a three-vertex part containing $0,1$ has internal weight twenty-one, a part of three clique vertices has internal weight eighteen, and every other possibility has at most these amounts. In the second case a pair $\{0,1\}$ can contribute fifteen and the other pair six, totaling twenty-one; if that pair is absent, two pairs contribute at most twelve. Thus internal weight is at most twenty-one in every case. It is attained by $\{0,1\},\{2,3\},\{4\}$. Minimum crossing weight is therefore $51-21=30$ and partition cost is sixty. The repeated-splitting algorithm has strict ratio $66/60=11/10$.

First gap and audit

The primary opening talk on printed page 2901 was inspected. This counterexample concerns a natural algorithm even in the symmetric graph-cut subclass, where better methods may exist; it is not a hardness result or a claim about the current status of the three-part problem. Choosing each cut optimally does not optimize the interactions between the eventual parts. General algorithms would need a joint partition argument or a different representation of those interactions. The audit checked nonempty parts, the doubled cut objective, the unique first split, and both possible part-size patterns. No machine search or oracle experiment was used. The general fixed-$k$ complexity question remains unresolved in this attempt.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The exact two-part identity does not extend through greedy splitting; the general fixed-k algorithm or lower bound remains missing.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. The exact two-part identity does not extend through greedy splitting; the general fixed-k algorithm or lower bound remains missing.