Polynomial Space Counting Problems
1989; Society for Industrial and Applied Mathematics; Volume: 18; Issue: 6 Linguagem: Inglês
10.1137/0218073
ISSN1095-7111
Autores Tópico(s)Complexity and Algorithms in Graphs
ResumoThe classes of functions $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ that are analogous to the class $# P$ are defined. Functions in $# \textit{PSPACE}$ count the number of accepting computations of a nondeterministic polynomial space bounded Turing machine, and functions in $\natural \textit{PSPACE}$ count the number of accepting computations of nondeterministic polynomial space bounded Turing machines that on each computation path make at most a polynomial number of nondeterministic choices. In contrast to what is known about $# P$, exact characterizations of both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ are found. In particular, $# PSPACE = FSPACE$ (the class of functions computable in polynomial space) and $\natural PSPACE = FSPACE (poly)$ (the class of functions computable in polynomial space with output length bounded by a polynomial). Both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ can be characterized by counting problems related to alternating Turing machines. Both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ have natural complete functions. It is an easy observation that $FP \subseteq # P \subseteq \natural \textit{PSPACE} $, where $FP$ is the class of functions computable in polynomial time. Relativization to oracles is considered, as are approximation techniques for obtaining a better understanding of whether either of the above inclusions is proper.
Referência(s)