ICC on Saturday

Detailed program
Saturday July 20th, 2002
See also the unified by-slot program

All sessions take place in auditorium 8.

Session 1

11:00-12:00  Paul J. Voda, Comenius U, Slovakia
Invited talk: Two simple intrinsic characterizations of main complexity classes
We give two simple uniform characterizations of the complexity classes L, NL, P, and NP by register machine programs. Both characterizations are intrinsic because they do not refer to any time and space bounds. The first characterization, which permits programs to peek into their computational history, captures also, Pspace and it is completely syntactical in that the restrictions on programs are decided from their syntax. The programs computing predicates of larger classes are permitted to access larger parts of their history. The second characterization restricts the access of programs to parts of their input which are then projected away by existential quantification.

12:00-12:30  Olivier Bournez, LORIA Nancy, France
Paulin de Naurois, LORIA Nancy, France
Jean-Yves Marion, LORIA Nancy, France
Safe recursion and calculus over an arbitrary structure
In this paper, we show that the Bellantoni and Cook characterization of the polynomial time computable functions in terms of safe recursive functions can be transfered to the model of computation over an arbitrary structure developed by L. Blum, M. Shub, and S. Smale. Hence, we provide an implicit complexity characterization of functions computable in polynomial time over any arbitrary structure.

Session 2

14:00-15:00  Carl Christian Frederiksen, U Copenhagen, Denmark
Neil D. Jones, U Copenhagen, Denmark
Invited talk: Program analysis for implicit computational complexity
This talk describes methods and practical work that brings together two lines: automatic estimation of program running times, and implicit computational complexity. Related work has been done by Bellantoni and Cook, Benzinger, Hofmann, Jones, Crary and Weirich, Leivant, Marion, Niggl, Schwichtenberg, and others. In this work we identify a decidable class of algorithms such that all can be executed within polynomial time (or logarithmic space). This class includes many natural algorithms that are used in solving real problems. The class is properly generalizes "safe recursion" and some related schemes provided by other researchers. Runtime bound information is extracted by program data-flow analysis algorithms that extend the "size-change" framework of our POPL 2001 paper to account for running times as well as termination. The analysis allows automatic detection of programs that are guaranteed to run (or be runnable) in polynomial time.

15:00-15:30  Lars Kristiansen, Oslo U College, Norway
New recursion-theoretic characterizations of well known complexity classes
In this paper we give recursion-theoretic characterizations of well-known complexity classes by schemes that neither contain bounds nor any kind of variable segregation. We prove that the class of problems decidable in logarithmic space is characterized by the closure of a neat class of initial functions (projections and constants) under composition and simultaneous recursion on notation. We also characterize the class of number-theoretic 0-1 valued functions computable in linear space as the 0-1 valued functions of the closure of a neat class of initial functions (projections and constants) under composition and simultaneous recursion.

Session 3

16:00-16:30  Klaus Aehlig, U Munich, Germany
Jan Johannsen, U Munich, Germany
An elementary fragment of second-order lambda calculus
A fragment of second-order lambda calculus (System F) is defined that characterizes the elementary recursive functions. Type quantification is restricted to be non-interleaved and stratified, i.e., the types are assigned levels, and a quantified variable can only be instantiated by a type of smaller level, with a slightly liberalized treatment of the level zero.

16:30-17:00  Karl-Heinz Niggl, Techn. U of Ilmenau, Germany
Control structures in programs and computational complexity
A key problem in implicit complexity is to analyse the impact on program run times of nesting (restricted) control structures, such as recursion in all finite types in functional languages or for-do statements in imperative languages. In particular, are there methods of extracting information from the syntax of such programs so as to distinguish programs that run in polynomial time from those that run in (iterated) exponential time? If so, is there a general rationale behind these methods that gives insight as to why some nesting of control structures may cause a blow up in complexity, while others do not? This paper integrates various recent solutions to these problems into a uniform approach to implicit complexity.