Fr, 09.02.2018, 13:30
type-two poly-time and length revisions

Referent: Dr. Florian Steinberg, INRIA
Raum: S2|15-201

"We present a new, and fairly simple characterization of the type-two poly-time computable functionals. While being machine based, it avoids the use of higher order objects as running times and instead uses an approach first put forward by Cook that sticks to first order functions to formulate time constraints. Cook's class is known to not only contain feasible operations and we thus impose further restrictions. The purpose of these restrictions is very simple: It is to avoid unbounded iteration of functional input. We prove that this leads to a subclass of all feasible functionals and that closing under composition leads back to the class of all feasible functionals. We also prove that the same is true for a more restrictive condition, namely for the notion of strong poly-time."
This is joint work with Bruce Kapron.



Fachbereich Mathematik
Technische Universität Darmstadt

Schlossgartenstraße 7
64289 Darmstadt

A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang