Polynomial space and nondeterministic polynomial space

Use the all-tape resource classes of The classes DTIME, NTIME, DSPACE, and NSPACE and the worst-case convention of Worst-case time and space complexity of a machine. Set $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}={\bigcup }_{k\ge 1}\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n^k),\mathrm{N}\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}={\bigcup }_{k\ge 1}\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n^k)\mathrm{.}$ Here $k$ ranges over integers. Membership requires one fixed finite-tape machine, one exponent and input-independent asymptotic constants. A deterministic machine must decide the language; a nondeterministic machine must halt on every branch and accept exactly when an accepting branch exists. Finitely branching all-halting computation trees are finite: if one were infinite, a node with infinitely many descendants would have a least-indexed child with infinitely many descendants, recursively producing an infinite branch. Thus finite maxima exist; this uses a fixed finite ordering of instructions, not AC.

Space counts distinct scanned tape/cell pairs, including the input tape and each initial head cell. Initially occupied but unvisited input cells are not automatically counted, as specified in Uniform asymptotic time space comparison. Reading the complete input costs $n$ cells, and storing it explicitly costs $O(n+1)$ space. For polynomial space we may enlarge any bound to an integer polynomial $S(n)=C(n+1{)}^k$ dominating $n+1$ and the number of tapes. Conversely such a bound is $O(n^k)$ for $n\ge 1$, so this gives the same unions. Short inputs, including the empty input, must still halt, but do not affect asymptotic class membership. This definition asserts no equality between PSPACE and NPSPACE.