# LOGSPACE vs. PTIME

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.