University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > From almost optimal algorithms to logics for complexity classes via listings and a halting problem

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity