P-nonuniform
From Wikipedia, the free encyclopedia
A family of Boolean circuits is P-uniform if a Turing machine given 1n can output the member of the family with n inputs in time polynomial in n. A problem is P-nonuniform if no family of minimal Boolean circuits for the problem is P-uniform.