![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Thursday 29 March 2012, 09:00-10:00
From almost optimal algorithms to logics for complexity classes via listings and a halting problem
- đ¤ Speaker: Chen, Y (Shanghai Jiao Tong University)
- đ Date & Time: Thursday 29 March 2012, 09:00 - 10:00
- đ Venue: Seminar Room 1, Newton Institute
Abstract
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}$.
Series This talk is part of the Isaac Newton Institute Seminar Series series.
Included in Lists
- All CMS events
- bld31
- dh539
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
Note: Ex-directory lists are not shown.