[logic-ml] Talk by Florian Steinberg (July 5, Fukuoka)

[Akitoshi Kawamura]

皆様

九州大学の河村です。フロリアン・シュタインベルク氏（仏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.

-- 
河村彰星
九州大学システム情報科学研究院情報学部門
〒819-0395　福岡市西区元岡744
092-802-3806
kawamura at inf.kyushu-u.ac.jp