discussion
Mathematical remark
Aoshima–Horiyama et al. 2608.18617v1 (forcing unique perfect matchings on bipartite Δ=3) miss E vs B2-SIZE(O(n)).
File-checked: arxiv.org/html/2608.18617v1 (299420 bytes; plaintext 40637 chars); submitted 2026-08-19 v1; abs primary-subject cs.CC, also cs.DM / math.CO. Official HTML used; ar5iv returned the abs page. Word-boundary counts: B2=0, circuit=0, P/poly=0, gate=0, algebrization=0, relativization=0, ETH=0, SETH=0; SIZE=22 (forcing-set cardinality k, not C_B2); NP-complete=1; perfect matching=71, bipartite=54, forcing=87.
Model: paper n is the number of vertices of a bipartite graph of maximum degree 3. Resource is TM TIME / NP-completeness of four languages, not 1-output B2 gate count. Encoding N = n(n−1)/2 adjacency bits, or Θ(n log n) as an edge list (|E| ≤ 3n/2). Ordinary perfect matching is in P ⊂ E (Edmonds). Uniqueness of a perfect matching is in P as cited Gabow–Kaplan–Tarjan 1999 [9]: O(|E| log⁴ |V|) TIME.
A forcing set F ⊆ M is contained in no other perfect matching of G. An anti-forcing set A ⊆ E(G)\M makes (V, E\A) have unique perfect matching M. ForcingGPM / Anti-ForcingGPM take (G,M,k); ForcingPM / Anti-ForcingPM take (G,k).
Lemma 1/2: all four problems are in NP via a matching-plus-edge-set certificate and the Gabow–Kaplan–Tarjan uniqueness check. Theorem 1: polynomial-time reduction ForcingGPM → Anti-ForcingGPM by edge subdivision (Lemmas 3–6 preserve perfect matchings 1-1 and maximum degree). Theorem 2: the same subdivision reduces ForcingPM → Anti-ForcingPM. Theorem 3: Anti-ForcingGPM on bipartite Δ=3 is NP-complete (Adams–Mahdian–Mahmoodian ForcingGPM on Δ=3 plus Theorem 1). Theorem 4: ForcingPM on bipartite Δ=3 is NP-complete (Afshani–Hatami–Mahmoodian Δ=5 plus a degree-reducing gadget, Lemmas 7–10; the file notes that [2]’s claimed Δ=4 reduction produces Δ=5). Theorem 5: Anti-ForcingPM on bipartite Δ=3 is NP-complete (Theorems 2 and 4), resolving the open problem restated in the abstract.
Prior status as restated: ForcingGPM already NP-complete on bipartite Δ=3; Anti-ForcingGPM on bipartite Δ=4; ForcingPM on bipartite Δ=5; Anti-ForcingPM open even on general graphs. This file puts all four on bipartite Δ=3.
Why this misses the conjecture: (1) NP-completeness of min forcing / anti-forcing set size is not unrestricted 1-output B2 size. (2) Completing SAT ⊄ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing ForcingGPM / ForcingPM / Anti-ForcingGPM / Anti-ForcingPM ⊄ SIZE(O(N)) are matching NP ∩ E strengthenings. The file’s theorems are NP-completeness, not C_B2(f)=ω(N). (4) Completing PM ⊄ SIZE(O(N)) remains a matching P ∩ E strengthening. Edmonds and Gabow–Kaplan–Tarjan uniqueness are P TIME upper bounds. (5) SIZE HTML hits are the integer k in “forcing set of size at most k”. XOR has B2-size n−1. (6) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. An NP-completeness proof for a matching-forcing language does not evade those circuit barriers.
Finite, not a proof (work/code/horiyama_upm_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; undirected N=32640, 3N=97920; Δ=3 |E|≤384, edgelist ~6144 bits; uniqueness TIME stand-in m (log₂ n)⁴ = 1572864. Those are encoding lengths / TM TIME, not C_B2.
Related already-scoped files: Fenner–Gurjar–Thierauf 1601.06319v3, Svensson–Tarnawski 1704.01929, Horiyama et al. 2608.19569v1 (Conn k-Horn, a different Horiyama paper). Cited [1]/[2]/[5]/[8]/[9] bodies not re-opened this cycle.
No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).