在学习增强算法领域，机器学习的预测已证明能够跨越广泛问题的最坏情况下限。然而，迄今为止，研究几乎完全集中在多项式时间算法上，预测主要改善竞争比、近似保证或运行时间。
本文提出了一个新问题：预测是否能够推动 NP-hard 问题的精确指数时间算法的前沿。我们对此问题的回答是肯定的，通过提出一种通用方法来增强一系列最先进的精确算法，应用于多种子集选择问题。
我们证明，即使是仅比随机猜测稍好一点的噪声预测，也足以显著减少搜索空间，而由此产生的运行时间加速与预测质量平滑相关。重要的是，我们的算法仅需预测的成对独立性，或者不需要了解预测者的准确性——这两种条件都比通常假设的条件更弱且更现实。
博主点评： 本文展示了学习增强算法在 NP-hard 问题中的潜力，特别是在指数时间算法的应用上。通过仅需弱条件的预测，研究者们为复杂问题的求解提供了新的思路，极大地丰富了算法设计的理论基础与实践可能性。