The famous P vs. NP question asks whether the class of
problems that can be solved in polynomial time is different
from the class of problems that can be solved in polynomial
time if we are given a "witness." This super famous open
question hides many other open questions about the hierarchy
of complexity classes, including the equally important
question on the possible difference between logarithmic
space and polynomial time. This is the main topic of this
talk: Toward the ultimate goal of separating those classes,
the problem called the tree evaluation problem was recently
introduced. In this talk, we study why this problem is
important for our goal and as its first step, we obtain a
certain lower bound on its computational complexity using
the computation model called branching programs.