gpt 6 astra pro attempt on CS-19

FPT versus W[1]

Definitions and mathematical statement

A parameterized decision problem is fixed-parameter tractable if it has a uniform algorithm taking time $f(k)n^c$, where $f$ is a total computable function and $c$ is independent of $k$. For the clique problem, $n=|V(G)|$ and a $k$-clique is a set of $k$ pairwise adjacent vertices. The equivalent concrete target is the nonexistence of \[ A,f,c\quad\text{with}\quad T_A(G,k)\le f(k)n^c \] for all finite simple $G$ and $1\le k\le n$. An $n^{g(k)}$ algorithm does not meet this condition. The conjectured separation is $\mathsf{FPT}\ne\mathsf{W[1]}$ in the standard uniform parameterized model.

Formulation and concept references: [S1].

Short English statement

Can the combinatorial difficulty of finding a clique be confined entirely to its requested size, leaving a fixed polynomial dependence on graph size?

Research attempt

Current frontier and source-status note.

The source's formulation is uniform FPT for clique, not a bound whose polynomial exponent depends on $k$. Recent parameterized reductions retain that distinction [S1]. The manuscript retained as [S2] was withdrawn in version 2 on 10 May 2026, with the author's notice reporting fundamental inaccuracies; it is not used as a collapse theorem [E1]. The conditional ETH connection below is kept separate from an unconditional separation. Its general background is the sparsification and exponential-time framework of [E2].

Attack route.

Colour coding can ensure distinct selected vertices but cannot enforce all clique edges by itself. A natural dynamic program instead merges partial cliques with identical sets of possible continuations. If only $f(k)n^c$ states survived, it would be FPT. The first attempt tests that hope with an explicit graph family producing too many exact continuation sets. The second reconstructs a conditional SAT reduction, paying attention to the arbitrary computable parameter factor. Neither argument is a lower bound against all deterministic algorithms.

Attempt: exact continuation states.

For a partial clique $S$ in a simple graph, put \[ C(S)=\bigcap_{v\in S}N(v). \] The possible extensions by $r$ more vertices are exactly the $r$-cliques in the induced graph on $C(S)$. This follows because a vertex in $C(S)$ is adjacent to all of $S$, and edges within the new set must still be checked. Chosen vertices themselves do not belong to $C(S)$, since the graph has no loops. Thus two partial cliques of the same size with the same $C(S)$ can legitimately share this dynamic-program state.

A sufficient algorithmic hypothesis would be a uniform bound \begin{equation}\label{wsref-0-65-71-37-36-3a-73-74-61-74-65-73} \#\{C(S):S\text{ a clique},\ |S|=i\}\leq f(k)n^c \qquad(0\leq i\leq k), \end{equation} for one fixed $c$ and a total computable $f$. If such a bound held with fixed $c$ and computable $f$, generate states by $C(S\cup\{v\})=C(S)\cap N(v)$ for $v\in C(S)$ and deduplicate their $n$-bit representations. At most $n$ transitions per state and polynomial bit-set costs would give a uniform FPT algorithm. The issue is the number of exact states, not the validity of this merging rule.

That count can be too large. Choose integers $t,m\geq2$ and disjoint sets $A_i=\{a_{i,1},\ldots,a_{i,m}\}$ for $1\leq i\leq t$. Join all pairs from different $A_i$, and no pairs inside an $A_i$. Add an independent witness set $B=\{b_{i,j}:1\leq i\leq t,1\leq j\leq m\}$. Join $b_{i,j}$ to every vertex of $\bigcup A_i$ except $a_{i,j}$. For each tuple $\mathbf j=(j_1,\ldots,j_t)$, $S_{\mathbf j}=\{a_{1,j_1},\ldots,a_{t,j_t}\}$ is a clique, and \begin{equation}\label{wsref-0-65-71-37-36-3a-73-69-67-6e-61-74-75-72-65} C(S_{\mathbf j})\cap B =B\setminus\{b_{1,j_1},\ldots,b_{t,j_t}\}. \end{equation} Different tuples give different continuation sets. This graph has $n=2tm$ vertices and at least $m^t$ states at level $t$, relevant for parameter $k=t+1$. For any fixed $c$, choose $t>c$ and let $m\to\infty$. Then $m^t/[f(t+1)(2tm)^c]\to\infty$ for every fixed finite value $f(t+1)$. Hence (eq76:states) is false for this exact-state method.

The graph is highly structured and its clique problem is easy. A symbolic representation could compress many of its states, so the example does not prove any general parameterized lower bound. It locates the precise failure in a particular FPT proposal. The companion script checks all $3^4=81$ signatures for $t=4,m=3$ directly from adjacency.

Attempt: a conditional ETH consequence with the quantifiers intact.

Assume sparse 3-SAT has a positive exponential-time lower bound: there are constants $C,\eta>0$ such that formulas with $N$ variables and at most $CN$ clauses cannot all be decided in $O(2^{\eta N}\operatorname{poly}(N))$ time. This is an unproved hardness hypothesis of the type obtained from ETH using sparsification [E2], not a theorem established here. Partition the clauses into $k$ blocks. For each block make one vertex for each truth assignment to the variables occurring in that block that satisfies all its clauses. There are at most $2^{3\lceil CN/k\rceil}$ such vertices per block. Join vertices in different blocks exactly when their assignments agree on shared variables. No edges are placed within a block.

A $k$-clique picks exactly one assignment per block, and pairwise agreement makes their union a well-defined assignment satisfying every clause. Conversely any satisfying assignment supplies such a clique. Thus the reduction is correct, with graph size \[ n\leq k\,2^{3\lceil CN/k\rceil}. \] Enumerating assignments and checking pairs costs at most $2^{O(CN/k)}\operatorname{poly}(N,k)$, with an absolute constant in the exponent. An FPT clique algorithm of time $f(k)n^c$ would solve these formulas in \[ f(k)k^c2^{3c\lceil CN/k\rceil} +2^{O(CN/k)}\operatorname{poly}(N,k). \] Choose one fixed integer $k$ sufficiently large that both exponential coefficients are below $\eta$. With that choice $f(k)$ is a fixed finite constant, however enormous. For sufficiently large $N$ this contradicts the assumed lower bound. Therefore sparse ETH implies the stated separation. This proof does not demand an unjustified effective estimate on the growth of the arbitrary total computable function $f$.

Stress test.

The reduction uses a fixed $k$ chosen after the proposed exponent $c$ and hardness constant $\eta$, not $k=N$ with an uncontrolled factor $f(N)$. It also includes graph-construction time. Dropping that cost can produce a spurious subexponential algorithm. The conclusion is conditional on ETH; using it as an unconditional proof would simply assume a different major complexity separation.

For colour coding, the probability that a fixed $k$-set receives distinct colours is $k!/k^k$. Repetition or perfect hash families can address that event but do not decide whether the selected vertices form a clique. In particular, colourful paths and colourful cliques impose different edge constraints. The exact-state example also cannot distinguish the power of an arbitrary compressed algebraic state or an entirely different algorithm. Uniformity, total computability of $f$, and a fixed exponent in $n$ remain part of the target throughout.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The naive common-neighbour state-count route is refuted by an explicit family, and the ETH-to-clique implication is proved with its size and parameter quantifiers exposed. Neither argument separates FPT from W[1] unconditionally or gives an FPT clique algorithm. A continuation needs a new compression mechanism escaping the explicit signatures, or a genuine unconditional hardness argument not supplied by ETH. No novelty claim is made for the standard conditional reduction.

Sources

• S1 Chen, Feng, Laekhanukit and Liu, Simple Combinatorial Construction, arXiv:2304.07516v2 $2024$. https://arxiv.org/html/2304.07516v2. Catalogue formulation source.
• S2 Sharp-W[1] = FPT: Fixed-Parameter Tractable Exact Algorithms for the #k-Matching Problem. https://arxiv.org/abs/2604.16308. Catalogue research/status reference; not a proof endorsement.
• S3 A Parameterized-Complexity Framework for Finding Local Optima. https://drops.dagstuhl.de/storage/00lipics/lipics-vol362-itcs2026/LIPIcs.ITCS.2026.66/LIPIcs.ITCS.2026.66.pdf. Catalogue research/status reference; not a proof endorsement.
• E1 Yongming Yi, Sharp-W[1] = FPT: Fixed-Parameter Tractable Exact Algorithms for the #k-Matching Problem, arXiv:2604.16308v2, withdrawal notice, 10 May 2026. https://arxiv.org/abs/2604.16308v2. Inspected 27 September 2026; the withdrawn claim in [S2] is retained as provenance, not treated as a theorem.
• E2 Russell Impagliazzo, Ramamohan Paturi and Francis Zane, Which Problems Have Strongly Exponential Complexity?, Journal of Computer and System Sciences 63 $2001$, 512--530, sparsification framework and ETH consequences. https://doi.org/10.1006/jcss.2001.1774. Sparse ETH is explicitly an extra assumption; the clause-block consistency reduction is proved in the notebook.