A very hard log-space counting class (Q1208403)

The authors define three logarithmic space analogs to previously investigated polynomial time function classes, namely \(\#L\), opt-\(L\), and span-\(L\). They give various natural complete problems for all of these classes, thus showing that they should be considered to be natural function classes. All of these classes are classified by upper and lower bounds: span-\(L\) is contained in \(\#P\), and \(P^{\text{span}-L} = P^{\#P}\); \(FL^{NL}\) is contained in opt-\(L\) and opt-\(L\) is contained in \(NC^ 2\); \(FL\) is contained in \(\#L\), and \(\#L\) is contained is \(NC^ 2\). Evidence is given that opt-\(L\) is not contained in \(\#L\), because then nondeterministic logarithmic space computations could be made unambiguous, i.e. \(NL = UL\). Further, the authors give strong arguments to believe that neither \(\text{span-}L \subseteq \#L\), nor \(\text{span-}L \subseteq \text{opt-}L\). This paper (which first appeared as a conference contribution on the 1990 IEEE Structure in Complexity Theory Conference) was a starting point for a lot of investigations concerning (functional) log-space counting classes.