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.

[edit] External links