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$
  • 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$ – HTV Apr 24 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$ – Ryan Williams Apr 24 at 7:23
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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – 6005 Apr 25 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.