Mathematical remark

Horiyama–Mineyoshi–Okura–Seto–Teruyama 2608.19569v1 (Boolean connectivity of k-Horn formulas) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.19569v1 (560214 bytes; plaintext 77183 chars); submitted 2026-08-20 v1; abs primary-subject cs.CC / listed in cs.DS. Official HTML used; ar5iv returned the abs page. Word-boundary counts: B2=0, circuit=0, P/poly=0, ETH=0, SETH=0, gate=0, algebrization=0, relativization=0; SIZE=3 (DNF size / characteristic-set size / permutation-set size O(n^{3k})); Boolean=42, Horn=128, connectivity=29, coNP=23, PSPACE=7, PPZ=15, SAT=16.

Model: paper n is the number of Boolean variables of a k-Horn CNF (at most one positive literal per clause). Resource is TM TIME, and P vs coNP-complete, for Conn k-Horn: whether the solution graph G_φ (satisfying assignments; Hamming-distance-1 edges) is connected. This is not 1-output B2 gate count. Input length is N=Θ(m k log n). Brute-force connectivity is 2^n poly(n,m) TIME, hence in E when N≥n. Horn-SAT is in P.

Theorem 1: Conn k-Horn in deterministic O*(2^{(1-1/(2k)) n}) TIME and polynomial space, via DetPPZ listing of locally minimal assignments (Lemma 8) plus Gopalan/Makino (Corollary 1: connected iff no locally minimal nonzero assignment). Theorem 2 ([9] Paturi–Pudlák–Zane): k-SAT in the same DetPPZ TIME. Lemma 1 ([6]): Conn k-Horn is coNP-complete for k≥3. Theorem 3: Conn k-Horn-2 in O(n^2) TIME. Theorem 4 / Corollary 5: Conn E3-Horn-3 in O(n^2) TIME; Conn Ek-Horn-k in P for k≥2. Theorem 5: DisConn 3-Horn-3 is NP-complete (from Monotone NAE E3-SAT-E4). Theorem 6: Conn 3-Horn-E3 is coNP-complete. Open: Conn E3-Horn-E4. Makino et al. [7] Conn k-CNF (k≥3) remains PSPACE-complete.

Why this misses the conjecture: (1) TM TIME / coNP-completeness of formula-connectivity is not unrestricted 1-output B2 size. (2) Completing SAT ⊈ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing CONN-k-HORN ⊈ SIZE(O(N)) is a matching coNP ∩ E strengthening. The file does not name C_B2. (4) Completing HORN-SAT ⊈ SIZE(O(N)) is a matching P ∩ E strengthening. (5) PPZ here lists locally minimal assignments. It is not a PPSZ depth-3 circuit bound. Completing a 2^{n/k} s_3^k bound is the already-scoped GKW / PPSZ ledger. (6) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. DetPPZ / self-implicating sets / NAE reductions do not evade those circuit barriers.

Finite, not a proof (work/code/horiyama_khorn_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; DetPPZ k=3 exponent 5/6 so 2^{213.33} TIME on 256 variables; E3-Horn-3 n=256 has m~256, N_bits~6912. Those are TM TIME / encoding lengths, not C_B2.

Related already-scoped files: GKW 1811.04828 (PPSZ as a depth-3 premise). Makino–Tamaki–Yamamoto [6,7], Paturi–Pudlák–Zane 1999 [9], Gopalan et al. [5], and Schwerdtfeger [13] bodies not retrieved.

No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).