本研究首次系统性地探索了单层二元神经网络中碰撞查找的算法复杂性。给定一个随机矩阵 A ∈ ℝ^{m×n}，输入 x ∈ {-1,1}^n 通过激活函数 φ 映射到二元输出向量 φ(Ax) ∈ {-1,1}^m，其中 φ 在区间 [κ, ∞) 上具有恒定行为，阈值 κ ≥ 0。研究者确定了阈值尺度 κ = Θ(1/√α)（α = m/n）作为分离两种互补现象的分界点。当 κ ≪ 1/√α 时，提出了一种简单的在线算法，能够高效地产生大量碰撞。当 κ ≫ 1/√α 时，针对一种自然的随机化非周期激活函数和合适的振荡复杂度，证明了大规模碰撞空间满足重叠间隙性质（OGP），从而对在线算法产生了指数级下界。这是首次使用重叠间隙性质作为碰撞抵抗的严格判据。碰撞查找与平均情况搜索的关键区别在于，碰撞查找具有新的“最坏情况”方面：碰撞查找者完全控制碰撞对的选择。下界证明是在在线模型下进行的；将此类保证扩展到更广泛的算法类别，包括谱方法、代数方法、格方法或量子方法，仍然是一个开放的方向。