Complete Problems of Propositional Logic for the Exponential Hierarchy http://arxiv.org/abs/1602.03050 NP完全にはSAT、多項式階層とPSPACEについてはQBF_kとQBFという論理学的な完全問題があるのに対して、指数階層には同様のものは考えられていなかったが、スコーレム関数の量化を許すよう拡張したQBFが同様に対応するというような話。 IF logic (Independence-friendly logic) の話なんかも出てきて、色々つながってるんやなぁ、という感じ。