论文标题
整数分解和Riemann的假设：为什么很难建立两个项目
Integer factorization and Riemann's hypothesis: Why two-item joint replenishment is hard
论文作者
论文摘要
具有定期重复事件的分销网络通常具有巨大的希望来利用规模经济。联合补充问题是捕获这些影响的库存管理，制造和物流中的基本模型。但是，找到一种有效解决这些模型的有效算法，或者表明不存在的算法长期以来一直是开放的，无论空的关节订单是否可能是可能的。无论哪种情况，我们都表明，仅使用两种产品找到最佳的联合补充实例解决方案至少与整数分解一样困难。据作者所知，这是第一次使用整数分解来解释任何形式的优化问题的计算硬度。在假设Riemann的假设是正确的假设下，我们实际上可以证明，在随机减少的情况下，可能是空的关节订购点可能具有空的关节订购点是NP完整的，这意味着甚至没有量子计算机也可能能够有效地解决它。通过将关节补充的计算复杂性与密码学，主要分解和质数的其他方面相关联，类似的方法可以帮助建立（整数分解）供应链管理及其他地区其他开放周期性问题的硬度，其解决方案已避免了标准方法。
Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are a fundamental model in inventory management, manufacturing, and logistics that capture these effects. However, finding an efficient algorithm that optimally solves these models, or showing that none may exist, has long been open, regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two products is at least as difficult as integer factorization. To the best of the authors' knowledge, this is the first time that integer factorization is used to explain the computational hardness of any kind of optimization problem. Under the assumption that Riemann's Hypothesis is correct, we can actually prove that the two-item joint replenishment problem with possibly empty joint ordering points is NP-complete under randomized reductions, which implies that not even quantum computers may be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish (integer factorization) hardness of additional open periodic problems in supply chain management and beyond, whose solution has eluded standard methods.
