gpt 6 astra ultra attempt on CS-18

The Unique Games Conjecture

Definitions and mathematical statement

For $[k]=\{1,\ldots,k\}$, a unique game has a nonempty finite edge set and a permutation $\pi_e$ of $[k]$ on each directed edge $e=(v,w)$. Its optimum is \[ \operatorname{val}(G)=\max_{L:V\to[k]}\frac{\#\{e=(v,w):\pi_e(L(v))=L(w)\}}{|E|}. \] For every fixed $\varepsilon,\delta>0$ with $\varepsilon+\delta<1$, some fixed $k$ makes distinguishing $\operatorname{val}(G)\ge1-\varepsilon$ from $\operatorname{val}(G)\le\delta$ NP-hard under deterministic polynomial-time many-one reductions. Intermediate values lie outside the promise. The alphabet size depends on the accuracy parameters, not on the growing input graph.

Formulation and concept references: [S1].

Short English statement

Is it computationally intractable to distinguish almost satisfiable permutation constraints from ones where almost none can be satisfied?

Research attempt

Scope, source check, and method.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. It studies whether the permutation structure makes almost satisfiable instances efficiently recognizable, beginning with exact satisfaction and then allowing a controlled number of cycle constraints. The original unweighted objective, fixed alphabet, deterministic reductions, and promise gap are retained. The source formulation is Khot's survey [S1].

The quantifier order is essential: for every fixed $\varepsilon,\delta>0$ with $\varepsilon+\delta<1$, the conjecture permits a sufficiently large but fixed alphabet $k=k(\varepsilon,\delta)$. A running time exponential in $k$ can still be polynomial in graph size for this question; a running time exponential in the number of graph edges cannot. Exact satisfaction, $\operatorname{val}(G)=1$, is a different problem from the completeness threshold $1-\varepsilon$.

The catalogue's 2-to-1-games source [S2] concerns a different constraint relation; it is not used as a proof of the permutation-constraint conjecture. Likewise conditional approximation consequences do not prove the hypothesis from which they follow. The present work uses direct elementary arguments rather than assuming a general approximation theorem. It makes no claim of historical novelty for the cycle or tree calculations.

Attack plan and conventions.

For an edge written $e=(v,w)$, its constraint is $L(w)=\pi_e(L(v))$. Traversing it backwards uses $\pi_e^{-1}$. Choose a spanning forest of the underlying undirected multigraph, ignoring loops for this purpose. Let $n=|V|$, $m=|E|>0$, and let $c$ count connected components, including isolated vertices. The forest has $n-c$ edges, and \[ q=m-n+c\ge0 \] counts the remaining edges. Distinct directed or parallel edges remain separate constraints in the objective. This convention also handles loops, which the literal catalogue definition does not exclude.

First, propagate one root label through each tree and inspect the remaining constraints. Second, keep only the endpoints of the $q$ nonforest edges as explicitly enumerated variables and optimize the forest conditionally by dynamic programming. This yields an exact algorithm with a transparent parameter dependence. The final test asks whether any of these arguments has the uniform scope needed for the UGC promise.

Lemma 29.1: exact satisfaction is a common-fixed-point test.

Root each forest component. For every vertex $v$ in a component, let $\sigma_v$ be the permutation obtained by composing edge permutations along the root-to-$v$ path, using inverses when needed. The root has $\sigma_{\mathrm{root}}=\mathrm{id}$. For every directed edge $e=(v,w)$ set \begin{equation}\label{wsref-0-61-32-39-3a-63-79-63-6c-65} \rho_e=\sigma_w^{-1}\pi_e\sigma_v. \end{equation} The component is exactly satisfiable if and only if $\bigcap_e\operatorname{Fix}(\rho_e)$ is nonempty, where the intersection ranges over its edges. All these sets can be computed in $O(k(m+n))$ permutation-table operations over the whole graph.

Proof. Once a root label $a$ is chosen, satisfying every forest edge forces $L(v)=\sigma_v(a)$ by induction along the tree. Substitution in an arbitrary remaining constraint gives $\pi_e\sigma_v(a)=\sigma_w(a)$, equivalently $\rho_e(a)=a$. Thus any satisfying labeling supplies a common fixed point. Conversely, a common fixed point and the displayed propagated labels satisfy all edges. The forest edges contribute identity permutations and hence no further restriction. Try all $k$ root labels independently in each component; there is no need to enumerate a product over components. Computing each composition or inverse and checking its fixed points costs $O(k)$, giving the bound. An isolated vertex has no restriction and any label works. A loop is treated by exactly the same fixed-point equation.$\square$

Testing each cycle separately is weaker than testing a common fixed point. For an explicit loop-free example on three labels, take two triangles sharing only a root vertex. Put identity permutations on the four edges of their spanning tree. On the two closing edges put respectively the transpositions $(1\ 2)$ and $(2\ 3)$. The first triangle is satisfiable with root label $3$, and the second with root label $1$. Each fundamental cycle therefore has a fixed point, but there is no root label fixed by both permutations. The complete six-edge instance is not exactly satisfiable. Assigning label $3$ to every vertex satisfies five edges, so its optimum is exactly $5/6$. This example rejects a weaker local consistency test while confirming the intersection in Lemma 29.1. It also shows why the labels at shared vertices cannot be optimized independently for different cycles. The tree dynamic program below keeps precisely those compatibility conditions rather than adding incompatible cycle optima.

Choosing an arbitrary root label in each component always satisfies the forest. Consequently every instance obeys \begin{equation}\label{wsref-0-61-32-39-3a-66-6f-72-65-73-74-62-6f-75-6e-64} \operatorname{val}(G)\ge\frac{n-c}{m} =1-\frac qm. \end{equation} For a family with $q/m\le\varepsilon$, this already certifies membership in the high-value side of the promise, irrespective of the cycle permutations. This is a structural sufficient condition, not a classifier for arbitrary instances with value near one.

An exact counterexample to the perfect-satisfaction shortcut.

Take a simple directed cycle of length $m\ge3$ on alphabet $\{1,2\}$. Put identity permutations on $m-1$ edges and the transposition on the last edge. The composed cycle permutation has no fixed point, so no labeling satisfies every edge. Removing any one edge leaves a path, which can be satisfied completely. It follows exactly that \[ \operatorname{val}(G)=1-1/m. \] For any fixed $\varepsilon>0$, sufficiently long cycles are therefore promised yes-instances of UGC while the exact-satisfaction algorithm rejects them. The obstruction occurs already with two labels and only one nonforest edge. The missing tolerance is not a numerical adjustment to the fixed-point test: it requires optimizing which constraints are allowed to fail.

Conversely a cycle is never a low-value instance when $m$ is large, because its spanning path already satisfies almost everything. A collection of solved special cases with this structure supplies no arbitrary-instance algorithm for separating the two promised ranges.

Lemma 29.2: exact optimization with few nonforest edges.

With the notation above, the optimum can be computed in \begin{equation}\label{wsref-0-61-32-39-3a-61-6c-67-6f-72-69-74-68-6d} O\left(k^{2q}\,k(m+n)\right) \end{equation} operations, apart from standard polynomial encoding overhead. In particular this is polynomial for fixed $k$ and $q$.

Proof. Let $B$ be the set of endpoints of nonforest edges, so $|B|\le2q$. Enumerate the $k^{|B|}$ assignments $a:B\to[k]$. For each one, the number of satisfied nonforest edges is already determined; this includes loops. The remaining task is to maximize satisfied forest edges subject to the pinned labels on $B$.

For a rooted tree, let $D_v(\alpha)$ be the best number of satisfied edges strictly inside the subtree rooted at $v$, given $L(v)=\alpha$ and all pins in that subtree. Set a forbidden pinned label to $-\infty$. For each child $u$ of $v$, let $\tau_{vu}$ be the permutation transporting a parent label to the child label required by the edge. It is either the stored permutation or its inverse. The recurrence is \[ D_v(\alpha)=\sum_{u\text{ child of }v} \max_{\beta\in[k]} \left(D_u(\beta)+\mathbf1_{\{\beta=\tau_{vu}(\alpha)\}}\right) \] for allowed labels at $v$. Distinct child subtrees have no common vertices, so their conditional choices are independent and the maxima add. Induction from the leaves proves the recurrence and its optimality.

Put $M_u=\max_\beta D_u(\beta)$. The inner maximum equals \[ \max\{M_u,\ D_u(\tau_{vu}(\alpha))+1\}. \] Although the first term includes the designated label without its bonus, that label's larger value is already included in the second term; hence this simplification does not create an unattainable larger score. It permits all $k$ parent-label values to be processed in $O(k)$ time per tree edge. Maximize at every root, add the component scores and the known nonforest score, and finally maximize over the enumerated pins.

Every global labeling restricts to one of the enumerated assignments on $B$, and the dynamic program gives the best forest completion for precisely that assignment. Conversely every dynamic-program completion and its pinned assignment is a valid global labeling. Thus the maximum is the true optimum, not just a relaxation. Each pin assignment costs $O(k(m+n))$, proving (a29:algorithm).$\square$

It is important that the tree program permits a forest edge to be violated. Insisting on satisfying the initially chosen forest would restrict the optimization and could miss a better tradeoff with the nonforest constraints. The root propagation in Lemma 29.1 was valid because that lemma assumed perfect satisfaction; it is not imposed in Lemma 29.2.

What the parameters do and do not prove.

If $k$ is fixed and $q=O(\log(m+n+2))$, the factor $k^{2q}$ is polynomial, so the algorithm covers a growing family beyond a bounded number of cycles. Its exponent depends on the fixed alphabet and the constant in that logarithm. For unrestricted input graphs, $q$ can be proportional to $m$, and the same formula is exponential. Almost satisfiability gives no bound of this sort on $q$: a dense graph with every edge permutation equal to the identity is perfectly satisfiable and can have many independent cycles.

In the loop-free subclass, independent uniformly random labels satisfy each edge with probability $1/k$, so averaging gives $\operatorname{val}(G)\ge1/k$. This explains why a small soundness threshold requires attention to alphabet size. The statement is deliberately restricted to distinct-endpoint edges: a loop with a fixed-point-free permutation has satisfaction probability zero. The fixed-point and dynamic-program algorithms above do not need this loop-free restriction and remain valid for the literal recorded scope.

Even a polynomial-time algorithm for the entire promised problem would contradict its NP-hardness only under $\mathsf P\ne\mathsf{NP}$; the catalogue states NP-hardness, not that assumption as an extra axiom. Here there is not even such a general algorithm. The result is a parameterized exact procedure, whose exponential factor is visible and uncontrolled on the conjecture's full class of graphs.

Verification, remaining gap, and outcome.

The companion checks enumerate small binary-label graphs and permutation assignments, compare the cycle test and dynamic program against brute-force optima, and include loops, reverse orientations, disconnected vertices, and frustrated cycles. Additional three-label cases test noncommuting permutations and the order of composition in (a29:cycle). All scores are integer counts before division by $m$, so no rounding tolerance enters. The long-cycle values are also checked separately.

UNRESOLVED. The proved work is the exact common-fixed-point criterion, the forest lower bound, and an exact algorithm parameterized by alphabet size and feedback-edge count. The cycle family explicitly defeats using perfect satisfaction as the near-satisfaction test. A positive UGC proof still needs reductions with the stated completeness, soundness, and fixed-alphabet quantifiers. An algorithmic challenge still needs a polynomial-time method for unrestricted graphs at the relevant fixed parameters. The present cycle enumeration has no such bound, and none of these elementary calculations is claimed as a new general approximation result.

Sources

• S1 Subhash Khot, On the Unique Games Conjecture, author-hosted survey. https://cs.nyu.edu/~khot/papers/UGCSurvey.pdf. Formulation source.
• S2 Towards a Proof of the 2-to-1 Games Conjecture. https://theoryofcomputing.org/articles/v021a011/v021a011.pdf. Further reference; not a proof endorsement.
• S3 An Approximate Solution to the Minimum Vertex Cover Problem: The Hallelujah Algorithm. https://www.preprints.org/manuscript/202510.2392. Further reference; not a proof endorsement.
• S4 Vertex Cover Might be Hard to Approximate to within 2-epsilon. https://cims.nyu.edu/~regev/papers/vc_hard.pdf. Further reference; not a proof endorsement.
• S5 Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT. https://arxiv.org/abs/2608.00333. Further reference; not a proof endorsement.