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

• Chen, Y (Shanghai Jiao Tong University)
• Thursday 29 March 2012, 09:00-10:00
• Seminar Room 1, Newton Institute.

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:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.