本文介绍了一种使用具有访问分离预言机的内存受限算法来解决给定集合中的点的 Oracle 复杂性下界的方法。作者证明了对于准确度 ε≥e^(-d^(o (1))) 的可行性问题，确定性算法要么使用 d^(1+δ) bits 的内存，要么至少需要进行 1/(d^(0.01δ)ε^(2 ((1-δ)/(1+1.01δ))-o (1))) 次预言机查询，随机算法要么使用 d^(1+δ) 的内存，要么至少需要进行 1/(d^(2δ)ε^(2 (1-4δ)-o (1))) 次查询。结果表明梯度下降算法在 Oracle 复杂性 / 内存权衡中是帕累托最优的，并且如果算法在 d 维中具有小于二次的内存，则确定性算法的 Oracle 复杂性总是多项式级别的 1/ε。