数え上げ計算モデルの計算能力について

概要

論文の詳細を見る
本稿では, 数え上げ問題に内在する計算構造が強力な計算能力を持っていることを述べる.このことを端的に示す事実として, 適当な論理回路Cと適当な多項式p(n)ならびに存在記号と全称記号の有限回の組み合せを用いて, ψ(x^^→)≡∃_py^^→_1∀_py^^→_2・・・∃_py^^→_<k-1>∀_py^^→_kC(x^^→, y^^→_1, y^^→_2, ・・・, y^^→_<k-1>, y^^→_k)(ここで, ∃_py^^→は∃y^^→∈{0, 1}^<p(│x^^→│)>を略したものである;∀_py^^→も同様.)といった形式で定義できる任意の論理関数ψが, (s(C)+p(│x^^→│))^<O(1)>サイズ(s(C)は論理回路Cのサイズ)の積和標準形(和積標準形でもよい)のブール式ψと適当な多項式q(n)を用いて, ψ(x^^→)≡│{y^^→∈{0, 1}^<q(│x^^→│)>:ψ(x^^→, y^^→)=1}│mod2と表現できることを示す.本稿では, このような結果をオペレータを基盤にした枠組みに基づいて議論する.
1998-07-23