On Some Deterministic Space Complexity Problems
Jiawei Hong · SIAM Journal on Computing · 1982
In this paper we give a complete problem in ${\text{DSPACE}}(n)$. The problem is whether there exists a cycle in the connected component containing $(0,0, \cdots ,0)$ in the graph $G_p $ of the zeros of a polynomial P over $GF(2)$ under a suitable natural coding. Hence the deterministic space complexity of this problem is $O(n)$ but not $o(n)$. We give as well several problems for which we can obtain very close upper and lower deterministic space bounds. For example, the deterministic space complexity to determine whether there exists a cycle in the graph of the set of assignments satisfying a Boolean formula is $O(n/\log n)$ but not $o(n/\log ^2 n)$.