The linear complementarity problem (LCP) is for an input n×n real matrix~M and an n-dimensional real vector~q to ?nd non-negative vectors w and~z so that w−Mz=q and wTz=0. The latter complementarity condition makes the problem non-linear. Chung proved that in general it is NP-hard to decide whether a solution exists. However, if (and only if) M~is a P-matrix, i.e., all its principal minors are positive, then a unique solution exists for any~q. Finding this solution is a prominent computational problem with embarrassingly open complexity. Neither hardness results nor polynomial algorithms are known. Megiddo showed that the problem, for input~M,~q, to ?nd a solution~w,~z, or a certi?cate that M~is not a P-matrix, cannot be NP-hard unless NP=co-NP.

I will discuss two combinatorial tools for describing and analysing pivoting algorithms for the LCP: unique-sink orientations of hypercubes, and complementary oriented matroids. I will show conditions on these combinatorial structures that correspond to various subclasses of the class of P-matrices (such as K-matrices, hidden-K-matrices). These subclasses have been studied before and polynomial algorithms are known. Our setting provides a new, simpli?ed analysis of the algorithms.

Various results are joint work with Komei Fukuda, Bernd Gärtner, Lorenz Klaus, Hans-Jakob Lüthi and Markus Sprecher.