ملخص: 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 XCuni.

لغة: إنجليزية