Algebraic properties of the first-order part of a problem
Not on the map. Why?
Abstract (arXiv)
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 mathbbN 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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). First posted on arXiv 30 Mar 2022.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 0; 2026: 1.
2 papers.
- 2023On the Complexity of Computing G"odel Numberscited by 0
- 2026Uniform Computability of PAC Learningcited by 0
- 2026Uniform Computability of PAC Learning26 Jan 2026
- 2023On the Complexity of Computing G"odel Numbers8 Feb 2023