From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem
Yijia Chen, Jörg Flum · Journal of the ACM · 2012
Let C denote one of the complexity classes “polynomial time,” “logspace,” or “nondeterministic logspace.” We introduce a logic L (C) inv and show generalizations and variants of the equivalence ( L (C) inv captures C if and only if there is an almost C-optimal algorithm in C for the set Taut of tautologies of propositional logic). These statements are also equivalent to the existence of a listing of subsets in C of Taut by corresponding Turing machines and equivalent to the fact that a certain parameterized halting problem is in the parameterized complexity class XC uni .