线性互补问题（LCPs）中，具有充分矩阵的子类扮演着重要角色。当前仍未解决的一个重要问题是这类问题是否能在多项式时间内被解决。Kojima、Megiddo、Noma 和 Yoshise 在1991年提出了一种内点算法（IPA），能够在输入大小和系数矩阵 $ \tilde{\nu}(M) $ 的多项式界限内解决 LCP。然而，这个值在比特编码长度中可能呈指数级增长。实际上，之前没有已知的关于 $ \tilde{\nu}(M) $ 的上界。我们解决了 de Klerk 和 E.-Nagy（2011年，数学规划）提出的一个开放问题，给出了 $ \tilde{\nu}(M) $ 在 $M$ 的比特复杂性中的指数上界。这一结果基于对充分矩阵的新特征描述，并且还提供了对 Väliaho 定理的简单新证明，该定理论述了充分矩阵与 $ \text{P}^* $ 矩阵之间的等价性。我们定义了 $ \tilde{\nu}^{\bigstar}(M) $，作为在正对角矩阵重缩的情况下可实现的最佳障碍数。我们的第二个主要结果是针对充分矩阵的 LCP 的一种算法，其运行时间在输入大小和优化值 $ \tilde{\nu}^{\bigstar}(M) $ 的多项式界限内。该算法基于观察到的近最优行重缩形成的凸集，结合了在行重缩集上的椭球法和一个依赖于矩阵障碍数的 IPA。如果 IPA 未能在期望的运行时间内解决 LCP，它将为椭球法提供一个分离 oracle，以找到更好的重缩。
博主点评： 这项研究通过提供充分矩阵的障碍数的上界以及新的算法，推动了线性互补问题的理论与实践进展，展现了在复杂性理论中探索深度的潜力。对算法的创新与思路的突破为未来的研究提供了重要参考。