7
$\begingroup$

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:

$L \in \mathsf{StreamL}$ if there exists a Turing machine $M$ which decides $L$, where:

  • There are two tapes, the read-only input tape and the working tape

  • $M$ moves only to the left on the input tape, and uses at most $O(\log n)$ space on the working tape.

Has this class been studied?


My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.

Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle structural complexity i.e. defining classes such as the above and determining their relationships.

There is also a large body of work on communication complexity classes. In this domain there is a relevant class called $\mathsf{P}^{cc}$ (see Babai, Frankl, and Simon 1986: Complexity classes in communication complexity theory), which contains functions of two variables $f(x,y)$ where they can be solved using a small amount of communication between $x$ and $y$. This is related to $\mathsf{StreamL}$ above (for functions of two variables, $\mathsf{StreamL}$ is contained in $\mathsf{P}^{cc}$), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.

The obvious inclusions are $\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$, and no apparent inclusion either way between $\mathsf{StreamL}$ and $\mathsf{NC}^1$.

$\endgroup$
2
  • 1
    $\begingroup$ I don't think there are many studies on this. It seems to me that for most purposes, we still study the one-way communication complexity which can be applied to proving lower bound for streaming algorithms. $\endgroup$ Commented Apr 24, 2020 at 2:47
  • 1
    $\begingroup$ Using the diajointness function (an AND of ORs) you can construct functions in NC1, even in AC0, that is not in StreamL (for communication complexity reasons). StreamL would be a very weak class indeed. $\endgroup$ Commented Apr 24, 2020 at 7:23

1 Answer 1

11
$\begingroup$

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.

Search for "one-way logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover what you need.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you for the answer. Indeed, the class is called $1L$ and is studied by Hartmanis and others, e.g. Hartmanis and Mahaney, 1981: Languages simultaneously complete for one-way and two-way log-tape automata. Here is a related question. $\endgroup$ Commented Apr 25, 2020 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.