Class Description

PIO: Polynomial Input Output

The class of function problems, f:{0,1}n->{0,1}m, such that f(x) is computable in time polynomial in n and m. Allows us to discuss whether a function is "efficiently computable" or not, even if the output is too long to write down in polynomial time.

Defined in [Yan81].

Strictly contains PINC.

Linked From

PINC: Polynomial Ignorance of Names of Classes

(Actually, I've since been informed that PINC means "Incremental Polynomial-Time.")

The class of function problems, f:{0,1}n->{0,1}m, such that the kth output bit is computable in time polynomial in n and k.

Defined in [JY88].

Contained in PIO. This containment is strict, since if m=2n (say), then computing the first bit of f(x) might be EXP-complete.

More about...