Consider the problem of determining the pivot sequence used by the Gaussian Elimination algorithm with Partial Pivoting (GEPP). Let N stand for the order of the in- put matrix and let e be any positive constant. Assuming PNC, we prove that if GEPP were decidable in paral- lel time N1/2- then all the problems in P would be char- acterized by polynomial speedup. This strengthens the P- completeness result that holds of GEPP. We conjecture that our result is valid even with the exponent 1 replaced for 1/2, and provide supporting arguments based on our result. This latter improvement would demonstrate the optimality of the naive parallel algorithm for GEPP (modulo PNC).