Abstract
Space efficient algorithms have been actively (again) studied from requirements in practical applications. In particular, we consider here sublinear working space and polynomial-time algorithms w.r.t. an input size parameter specified by each problem. Investing the possibility of having such algorithms is also an important and interesting topic in computational complexity theory, in particular, for understanding the nature of "computation." We survey some recent results and discuss some open questions from the view point of computational complexity theory.