Interpretation of programs, a tool to measure their complexity

Description:  In general, computing the complexity of a program is undecidable. However, in some restricted cases, we can provide some complexity bounds. One way is the use of interpretations. We show that these can be employed to get characterizations of the complexity classes LOGSPACE, PTIME, NPTIME and PSPACE. We propose a visit of these classes. Area(s): LOGIC AND COMPUTATION Date:  2007-06-13 Start Time:   14:00 Speaker:  Guillaume Bonfante (LORIA, Nancy) Place:  Sala 5.4 See more:   <Main>