クエリー記号付きブール式の計算複雑さ

点击翻译按钮获取中文摘要

カナダ・オタワ大学准教授のヤマカミトモユキ氏と研究のアイデアを交換した.以下の研究ノート[1]を執筆した.[1]"Quantified Boolean Formulas and Hyper Polynomial Hierarchies"(2000).その概要は以下のとおり.S.Fenner,S.Homer,R.Pruim,M.Schaeferは超多項式階層を導入することにより,PH(多項式時間階層)とPSPACE(多項式記憶域計算可能集合族)の中間領域を調べた.これは,帰納的関数論における超算術的階層の理論を計算量理論において展開する試みである.我々はノート[1]において,クエリー記号付きブール式を応用することにより,超多項式階層をより簡明に構成した.超多項式階層を構成する上で重要なのはリミット・ステージの処理のしかたである.リミット・ステージを処理するための道具として,我々は交付申請書の研究実施計画の欄で述べた概念「fQBF」を用いた.以下にfQBFの定義のあらましを記す.Quantifier付きブール式で真なもの全体の集合をQBFで表す.各自然数kに対してQBFの元のうちΣk型のもの全体の集合をkQBFで表す(kQBFはΣk完全集合,QBFはPSPACE完全集合であることが知られている).さて,fを自然数から自然数への関数とする.fQBFを以下のように定める.各quantifier付きブール式Φに対し,「Φ∈fQBF」⇔「∃k[Φ∈kQBF,k≦f(|Φ|)]」ただし|Φ|はΦの長さ.