Linear Complementarity Problems (LCPs) with sufficient matrices represent an important subclass of LCPs, and a significant open question remains whether these problems can be solved in polynomial time. Kojima, Megiddo, Noma, and Yoshise introduced an Interior Point Algorithm (IPA) in 1991, which can solve LCPs with sufficient matrices in time that is polynomially bounded by the input size and the handicap number $ \tilde{\nu}(M) $ of the coefficient matrix $M$. However, this value can be exponentially large in the bit encoding length. In fact, no upper bounds were previously known for $ \tilde{\nu}(M) $. We settle an open question raised by de Klerk and E.-Nagy (Math Programming, 2011) by providing an exponential upper bound on $ \tilde{\nu}(M) $ in the bit-complexity of $M$. This is based on a new characterization of sufficient matrices, which also leads to a simple new proof of Väliaho's theorem on the equivalence of sufficient and $ \text{P}^* $-matrices (Linear Algebra and its Applications, 1996). We define $ \tilde{\nu}^{\bigstar}(M) $ as the best possible handicap number achievable under rescaling the rows and columns by a positive diagonal matrix. Our second main result is an algorithm for LCPs with sufficient matrices, where the running time is polynomially bounded in both the input size and the optimized value $ \tilde{\nu}^{\bigstar}(M) $. This algorithm is based on the observation that the set of near-optimal row-rescalings forms a convex set. It combines the Ellipsoid Method over the set of row rescalings with an IPA whose running time depends on the handicap number of the matrix. If the IPA fails to solve the LCP in the desired running time, it provides a separation oracle to the Ellipsoid Method to find a better rescaling.
Blogger's Review: This research advances the theory and practice of linear complementarity problems by providing an upper bound on the handicap number of sufficient matrices and a new algorithm. The innovations in the algorithm and the breakthroughs in thought offer significant references for future studies in complexity theory.