Streaming problems are algorithmic problems that are mainly characterized by their massive
input streams. Because of these data streams the algorithms for these problems are forced to
be space-efficient as the input stream length generally exceeds the available storage. The
goal of this study is to analyze the impact of additional information (more specifically a
hypothesis of the solution) on the algorithmic space complexities of several streaming
problems. To this end different streaming problems are analyzed and compared. The two problems
most frequent item and number of distinct items with many configurations of different result
accuracies and probabilities are deeply studied. Both lower and upper bounds for the space and
time complexity for deterministic and probabilistic environments are analyzed with respect to
possible improvements due to additional information. The general solution search problem is
compared to the decision problem where a solution hypothesis has to be satisfied.
