有名なP対NP問題は，多項式時間で解ける問題のクラスと証拠が
あれば多項式時間で証拠の正しさを確かめることの出来るクラス
の違いを論じている．この極めて有名な課題の陰に隠れてしまって
はいるが，問題の複雑さに関しては他にも多くの重要な未解決問題
がある．本講演ではその中の一つである，対数領域と多項式時間の
違いに関する未解決問題に挑戦する．最近提唱された木評価問題と
呼ばれる計算問題の計算複雑さを解明することがこの未解決問題の
解決につながることを示し，その第一歩として，本問題の計算量の
下限に関して分岐プログラムと呼ばれる計算モデルを使って議論する．