polynomialsize

Polynomialsize is a term used in computational theory to describe resource bounds that grow no faster than a polynomial in the input length. In formal terms, a function s(n) has polynomial size if there exists a constant k and a constant c such that s(n) ≤ c n^k for all sufficiently large n. The notion most commonly appears in the context of circuit complexity and proof systems.

In the circuit model, a language L is said to have polynomial-size circuits if there exists a family of Boolean circuits {C_n} where each C_n has size at most p(n) for some polynomial p, and C_n correctly decides membership in L for all inputs of length n. This nonuniform perspective leads to complexity classes such as P/poly, the class of languages decidable by polynomial-size circuit families.

Polynomial size is distinct from polynomial time. Polynomial size concerns the description length or size of a circuit or proof, rather than the time a single uniform algorithm takes to run. It is, however, closely related to nonuniform vs uniform complexity: a polynomial-time algorithm can often be used to generate a polynomial-size circuit, but the two notions are not equivalent without additional structure.

In proof systems and formal verification, a statement may have polynomial-size proofs, meaning the length of the proof is bounded by a polynomial function of the statement’s length. This usage parallels the circuit context, highlighting a focus on descriptive or resource-bounded representations rather than on sequential computation alone.

Overall, polynomialsize serves as a foundational measure for classifying nonuniform computational resources and is contrasted with exponential size and with polynomial-time computation.