BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:From almost optimal algorithms to logics for complexity classes vi
 a listings and a halting problem - Chen\, Y (Shanghai Jiao Tong University
 )
DTSTART:20120329T080000Z
DTEND:20120329T090000Z
UID:TALK37155@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Let $C$ denote one of the complexity classes ``polynomial time
 \,'' ``logspace\,'' or ``nondeterministic logspace.'' We introduce a logic
   $L(C)_{mathrm{inv}}$ and show generalizations and variants of the  equiv
 alence ($L(C)_{mathrm{inv}}$ captures $C$ if and only if there  is an almo
 st $C$-optimal algorithm in $C$ for the set TAUT of  tautologies of propos
 itional 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}_{\nm uni}$.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR