限量子付きブール式の充足可能性問題に対する非線型下界

研究

Quantified boolean formula problem （の一般化）がおよそ n log n 時間の非線型下界を持つ，という結果です．QBF問題自体はPSPACEに入ることしか知られていませんが，こんな自然な問題の非線形下界が出るというのは非常に驚きです．どうやら交代性機械からQBFへの線型時間帰着と交代性機械による決定性機械の効率の良いシミュレーションを組合せて下界を導出しているようです．論文本体は10ページと短く，議論もそんなに複雑ではないようです．