We show that if and , then , where ⋆ and ◇ are the following operations in the Weihrauch lattice: ⋆ is the compositional product, which allows the use of two principles in sequence, while the diamond operator ◇ allows an arbitrary but finite number of uses of the given principle in sequence. This answers a question of Pauly.
V.Brattka, D.D.Dzhafarov, A.Marcone and A.Pauly, Measuring the complexity of computational content: From combinatorial problems to analysis (Dagstuhl Seminar 18361), Dagstuhl Reports8(9) (2019), 1–28, http://drops.dagstuhl.de/opus/volltexte/2019/10327. doi:10.4230/DagRep.8.9.1.
2.
V.Brattka, G.Gherardi and A.Pauly, Weihrauch Complexity in Computable Analysis, available at: arXiv:1707.03202.
3.
V.Brattka and A.Pauly, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci.14(4) (2018), 4.
4.
D.R.Hirschfeldt and C.G.Jockusch Jr., On notions of computability-theoretic reduction between principles, J. Math. Log.16(1) (2016), 1650002. doi:10.1142/S0219061316500021.
5.
E.Neumann and A.Pauly, A topological view on algebraic computation models, J. Complexity44 (2018), 1–22. doi:10.1016/j.jco.2017.08.003.
