Polynomial-time combinatorial operators are polynomials
[For the entire collection see Zbl 0753.00018.] A number-theoretic combinatorial function is of the form \(f(n)=\sum c_ i n!/(n-i)! i!\) where all the \(c_ i\) are non-negative (and similarly for several variables). Myhill and Nerode developed a substantial theory of combinatorial functions on the recursive equivalence types (which are a recursive analogue of cardinal numbers). The present authors develop an analogous class of functions (in fact, functors) on the polynomial-time equivalence types (PETs) which were introduced by Remmel and Nerode. The present paper shows that these analogues reduce to polynomials, that is, only a finite number of the \(c_ i\) are non-zero.
This page was built for publication: Polynomial-time combinatorial operators are polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035306)
