皆様
九州大学の河村です。フロリアン・シュタインベルク氏(仏INRIA)の講演を 以下のように開催いたしますので、お近くの方はどうぞお越しください。 http://www.fc.inf.kyushu-u.ac.jp/seminars/H300705.html
日時 July 5, 2018, Thursday, 16:40– 場所 Room 302, Ito Campus West Building II, Kyushu University (九州大学伊都キャンパスウエスト二号館302講義室)
Type-two poly-time and length revisions Florian Steinberg (Institut National de Recherche en Informatique et en Automatique)
The talk presents an alternate characterization of type-two polynomial-time computability, with the goal of making second-order complexity theory more approachable. The characterization relies on the usual oracle machines to model programs with subroutine calls, but the use of higher-order objects as running times is avoided. This is achieved by refining the notion of oracle-polynomial-time introduced by Cook by imposing a further restriction on the oracle interactions. Both the restriction as well as its purpose are very simple: it is well-known that Cook's model allows polynomial depth iteration of functional inputs with no restrictions on size, and thus does not guarantee that operators from the class preserve polynomial-time computability. We restrict the number of lookahead revisions, that is the number of times a query can be asked that is bigger than any of the previous queries and prove that this leads to a class of feasible functionals. Furthermore, all feasible problems can be solved within this class if one is allowed to separate a task into efficiently solvable subtasks. More formally put: the closure of the class under lambda-abstraction and application includes all feasible operations. This has consequences for a very similar class of strongly polynomial-time computable operators previously considered by Kawamura and Steinberg: It turns out to have the same closure property. This can be attributed to properties of the limited recursion operator, which is not strongly polynomial-time computable but decomposes into two such operations and lies in the broader class.