Time and Space

Eyal Kushilevitz, Noam NisanCambridge 1996 · DOI · OpenAlex

Abstract

In many models of computation it is possible to imagine communication between different stages of the computation. This communication is usually realized by one part of the computation leaving the computing device in a certain state and other part of the computation starting from this state. The amount of information “communicated” this way can often be quantified as the “space” of this model; and the number of times such a communication takes place relates to the “time” of the model. We then usually get time–space tradeoffs by utilizing communication complexity lower bounds. In this chapter we discuss several lower bounds concerning time and space in several models of computations. Particularly, certain types of Turning machines, finite automata, and branching programs.
BibTeX
@inproceedings{kushilevitz1996time,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {{Time and Space}},
  booktitle = {Cambridge},
  year = {1996},
  doi = {10.1017/cbo9780511574948.013},
}

Loading related content...

Figure