Bridging Probability and Computation: Optimal Parallel Search Under Dual Asymmetry

We address a fundamental gap in parallel computing theory: how to partition search spaces when both success probability and verification cost vary systematically with position. While existing work handles machine heterogeneity or data asymmetry separately, we provide the first unified treatment of uncertainty asymmetry (probability decay) and effort asymmetry (cost growth). Our closed-form solution θ * = 1 1+α-β -where α measures probability decay and β measures cost growth-optimally balances these dual asymmetries. Applied to large-scale integer factorization (128-bit numbers), with empirically measured α = 1.23 and β = 0.48, we obtain θ * = 0.727, yielding 4.8× speedup on 8 cores (38% better than uniform partitioning). Beyond factorization, our framework provides principled guidance for SAT solving, graph problems, and database search, establishing a new paradigm for uncertainty-aware parallel algorithm design.