Algebraic properties of the first-order part of a problem
share
In this paper we study the notion of first-order part of a computational problem, first introduced by Dzhafarov, Solomon, and Yokoyama, which captures the "strongest computational problem with codomain ℕ that is Weihrauch reducible to f". This operator is very useful to prove separation results, especially at the higher levels of the Weihrauch lattice. We explore the first-order part in relation with several other operators already known in the literature. We also introduce a new operator, called unbounded finite parallelization, which plays an important role in characterizing the first-order part of parallelizable problems. We show how the obtained results can be used to explicitly characterize the first-order part of several known problems.
READ FULL TEXT
