The Smallest Computational Complexity for the Linear Complementarity Problem with P-Matrix

The linear complementarity problem LCP(A, q) which consists of finding an real vector z such that Az+q>=0, z>=0, and z^T(Az+q)=0, where A and q are given real matrix and real vector respectively. When A is a P-matrix, LCP(A, q) is a NP-complete problem. Some traditional direct methods for solving the above problem need O(2^n n^2) or O(2^n n^3) number of arithmetic operations at least. This paper proposes a recursive algorithm for solving the LCP(A,q) with A is a P-matrix. The maximum computational complexity for proposed algorithm is not more than 0(2^n) which is the possible smallest computational complexity. And the average computational complexity for proposed algorithm is not more than O((3/2)^n). The proposed algorithm has simple structure and can be implemented easily.