n^2 log n might be in P but it is not polynomial. Need to update answer (and check regularity condition :P)