Algebraic properties of the first-order part of a problem

DOI10.1016/J.APAL.2023.103270MaRDI QIDQ6040614zbMATH OpenOpenAlexFDO

Authors Giovanni Soldà, Manlio Valenti

Publication date 19 May 2023

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.16298

zbMATH Keywords

computable analysisdegree-theoretic operationsWeihrauch reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Computation over the reals, computable analysis (03D78) Computability and recursion theory (03D99)

Abstract: 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.

Cites work

• A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
• A note on the diamond operator
• A topological view on algebraic computation models
• Closed choice and a uniform low basis theorem
• Completion of choice
• Effective Choice and Boundedness Principles in Computable Analysis
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• Leaf management
• Monte Carlo computability
• On notions of computability-theoretic reduction between Π21 principles
• On the algebraic structure of Weihrauch degrees
• On the topological aspects of the theory of represented spaces
• On the uniform computational content of computability theory
• On the uniform computational content of Ramsey's theorem
• On uniform relationships between combinatorial problems
• Probabilistic computability and choice
• Ramsey's theorem and products in the Weihrauch degrees
• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Subsystems of second order arithmetic
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• The weakness of being cohesive, thin or free in reverse mathematics
• Turing computability. Theory and applications
• Weihrauch Complexity in Computable Analysis
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(12)

• On the complexity of learning programs
• Countable ordered groups and Weihrauch reducibility
• The Weihrauch lattice at the level of \(\boldsymbol{\Pi }^1_1{-}\mathsf{CA}_0\): the Cantor-Bendixson theorem
• Indivisibility and uniform computational strength
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator
• Complemented subsets and Boolean-valued, partial functions
• Defining long words succinctly in FO and MSO
• On the first-order parts of problems in the Weihrauch degrees
• Sequential discontinuity and first-order problems
• The weakness of finding descending sequences in ill-founded linear orders
• The tree pigeonhole principle in the Weihrauch degrees

This page was built for publication: Algebraic properties of the first-order part of a problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6040614)