数列、ａ1,ａ2,ａ3, ... ,ａn が与えられたとき、全体の積がゼロになるかどうか判定する問題を考えます。

入力アルファベット Σ は数記号Σ1, 区切り記号 Σ2 , 終端記号 Σ3 からなり、
　Σ=Σ1∪Σ2∪Σ3 , Φ=Σ1∩Σ2∩Σ3 ,
Σ1 ＝｛0,1,2,3,4,5,6,7,8,9｝ , Σ2 ＝｛#｝ , Σ3 ＝｛$｝ とします。
入力ｘはｎ個の数値　αk∈Σ1Σ1* , (0<k<n）を # で区切り、文末に $ を加えたものとします。
したがって、ｘ＝ａ1#ａ2#ａ3# ... #ａn$　と表記できます。
２個のアルゴリズムを考えて見ます。
（アルゴリズム１）ａ＝ａ1×ａ2×ａ3× ... ×ａn　を計算する。
　　　　　　　　　ａ＝０？　の判定をする。
０ならば yes, ０でないならば no と答える。
（アルゴリズム２）入力数列中に ａk=０ をみたす k があるかどうか判定する。
　あれば yes , なければ no と答える。
ところで、アルゴリズム１と２では計算結果を得るまでに必要なステップ数はかなり違います。
アルゴリズム１では乗算が終了するまで解が得られませんが、アルゴリズム２は乗算を回避しています。

集合Ａ　＝｛ｘ｜ｘ＝ａ1#ａ2#ａ3# ... #ａn$ と表現でき ａ1×ａ2×ａ3× ... ×ａn＝０を満たす。｝
集合Ｂ ＝｛ｘ｜アルゴリズム１を実現するＴＭ　Ｍ１にxを与えたとき、Ｍ１が yes と答える。｝
集合Ｃ ＝｛ｘ｜アルゴリズム２を実現するＴＭ　Ｍ２にxを与えたとき、Ｍ２が yes と答える。｝

このとき集合Ａ、Ｂ、Ｃの計算量は違うということでしょうかどうでしょうか？
山口の理論によると、集合ＢとＣで計算量が異なると主張しているかに見えますが。
山口先生の支持者はどうお考えですか？