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 $\mathbb{N}$ 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.
翻译:问题的一阶部分的代数性质
翻译后的摘要:
本文研究了计算问题的一阶部分的概念,该概念是由Dzhafarov、Solomon和Yokoyama首次引入的, 它捕捉了“最强的计算问题,其余域为$\mathbb{N}$,并且可以通过Weihrauch约简到f”。此运算符对于证明分离结果非常有用,特别是在Weihrauch阶梯的较高级别。我们探讨了一阶部分与文献中已知的几个其他运算符的关系。我们还介绍了一种新的运算符,称为无限有界并行化,它在表征可并行化问题的一阶部分方面起着重要作用。我们展示了如何使用所获得的结果来明确表征几个已知问题的一阶部分。