MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The quest for VP-completeness

Meena Mahajan
IMSc Chennai
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Expert Audience
English

Date, Time and Location

Monday, 24 March 2014
10:10
60 Minutes
E2 1 - Bioinformatik
001
Saarbrücken

Abstract

Most complexity classes have several "natural" complete problems, and this is often taken as evidence of the "reasonableness" of the class itself. There is a distressing paucity of polynomial families complete for the class VP. This talk describes the quest for natural complete families for VP.

Contact

Markus Bläser
--email hidden
passcode not visible
logged in users only

Christine Kiesel, 03/19/2014 16:46
Christine Kiesel, 03/19/2014 16:36 -- Created document.