Hacker News Reader

Sorry, what's the significance of finiteness? The upper bound on an NFA is exponential steps of state transition splitting, thus P ⊆ NP ⊆ EXP, the class of exponential time algorithms.

View on HN

the finiteness, in a sense, makes it non-exponential. it boils down to the core characterstic of polynomials (equivalently "algebraic") of being finite series (compare with formal power series that don't have this limitation) of constant powers. Hence, given an input, you can get something that is a polynomial of that input, that makes it a finite sum of constant! powers of that input.

The sum is finite (vs formal power series which can be infinite) The powers are constant (this is what makes it non-exponential)

Reply on news.ycombinator.com