From almost optimal algorithms to logics for complexity classes via listings and a halting problem
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Mustapha Amrani.
Semantics and Syntax: A Legacy of Alan Turing
Let $C$ denote one of the complexity classes ``polynomial time,’’ ``logspace,’’ or ``nondeterministic logspace.’’ We introduce a logic $L©}$ and show generalizations and variants of the equivalence ($L©{mathrm{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 $mathrm{XC}_{
m uni}$.
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
