Weihrauch Complexity in Computable Analysis
From MaRDI portal
Publication:5024577
DOI10.1007/978-3-030-59234-9_11OpenAlexW2736063278MaRDI QIDQ5024577
Arno Pauly, Guido Gherardi, Vasco Brattka
Publication date: 26 January 2022
Published in: Theory and Applications of Computability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.03202
Related Items
An inside/outside Ramsey theorem and recursion theory ⋮ Effectivity and reducibility with ordinal Turing machines ⋮ Three topological reducibilities for discontinuous functions ⋮ Reduction games, provability and compactness ⋮ Effective aspects of Hausdorff and Fourier dimension ⋮ Non-collapse of the effective Wadge hierarchy ⋮ The computational strength of matchings in countable graphs ⋮ Algebraic properties of the first-order part of a problem ⋮ Primitive recursive reverse mathematics ⋮ Strong computable type ⋮ THE DISCONTINUITY PROBLEM ⋮ Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces ⋮ Notes on overt choice ⋮ Variations of statement, variations of strength. The case of the Rival-Sands theorems ⋮ On the complexity of learning programs ⋮ The complexity of finding supergraphs ⋮ Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective ⋮ Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations ⋮ Topological reducibilities for discontinuous functions and their structures ⋮ Unnamed Item ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 5--11, 2017 ⋮ Unnamed Item ⋮ Highness properties close to PA completeness ⋮ To reorient is easier than to orient: An on-line algorithm for reorientation of graphs ⋮ On the Weihrauch degree of the additive Ramsey theorem over the rationals ⋮ A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Closed choice and a uniform low basis theorem
- The weakness of being cohesive, thin or free in reverse mathematics
- Addendum to: ``The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Lipschitz continuous ordinary differential equations are polynomial-space complete
- Classical descriptive set theory as a refinement of effective descriptive set theory
- Binary subtrees with few labeled paths
- Towards computability of elliptic boundary value problems in variational formulation
- Borel complexity and computability of the Hahn-Banach theorem
- How incomputable is the separable Hahn-Banach theorem?
- A computable version of Banach's inverse mapping theorem
- First level Borel functions and isomorphisms
- Theory of representations
- Compactness in constructive analysis revisited
- Representations of the real numbers and of the open subsets of the set of real numbers
- Computable invariance
- Computability on subsets of Euclidean space. I: Closed and compact subsets
- Computability on subsets of metric spaces.
- Extended admissibility.
- On the uniform computational content of the Baire category theorem
- Comparing representations for function spaces in computable analysis
- A topological view on algebraic computation models
- On the uniform computational content of computability theory
- Quasi-Polish spaces
- Towards computable analysis on the generalised real line
- Joins in the strong Weihrauch degrees
- Probabilistic computability and choice
- Topological complexity with continuous operations
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Real hypercomputation and continuity
- On uniform relationships between combinatorial problems
- Diagonally Non-Computable Functions and Bi-Immunity
- Complexity theory for operators in analysis
- Reverse Mathematics of Matroids
- The Vitali Covering Theorem in the Weihrauch Lattice
- Parallel and Serial Jumps of Weak Weak König’s Lemma
- Many-one reductions and the category of multivalued functions
- STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES
- On the (semi)lattices induced by continuous reducibilities
- Weihrauch degrees, omniscience principles and weak computability
- Effective Choice and Boundedness Principles in Computable Analysis
- Computability of the Radon-Nikodym Derivative
- Effective Borel measurability and reducibility of functions
- On notions of computability-theoretic reduction between Π21 principles
- Computability and Analysis, a Historical Approach
- Computable Reductions and Reverse Mathematics
- Generalized Effective Reducibility
- Slicing the Truth
- On the existence of a connected component of a graph
- Degrees of Unsolvability: A Tutorial
- Weihrauch Degrees of Finding Equilibria in Sequential Games
- Effective Borel degrees of some topological functions
- Finite choice, convex choice and finding roots
- Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
- Undecidability in Weihrauch Degrees
- Borel Complexity of Topological Operations on Computable Metric Spaces
- Die Nichtkonstruktivität des Brouwerschen Fixpunktsatzes
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On the algebraic structure of Weihrauch degrees
- ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
- ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS
- Dividing by Zero -- How Bad Is It, Really?
- Descriptive Set Theory in the Category of Represented Spaces
- Monte Carlo Computability
- Revising Type-2 Computation and Degrees of Discontinuity
- The degree structure of Weihrauch-reducibility
- Levels of discontinuity, limit-computability, and jump operators
- Decomposing Borel functions using the Shore–Slaman join theorem
- Non-deterministic computation and the Jayne-Rogers Theorem
- Weihrauch and constructive reducibility between existence statements
- THE CHARACTERIZATION OF WEIHRAUCH REDUCIBILITY IN SYSTEMS CONTAINING
- Forests describing Wadge degrees and topological Weihrauch degrees of certain classes of functions and relations
- Connected choice and the Brouwer fixed point theorem
- Game characterizations and lower cones in the Weihrauch degrees
- A quasi-order on continuous functions
- On the complexity of the relations of isomorphism and bi-embeddability
- Cohesive avoidance and strong reductions
- ∏ 0 1 Classes and Degrees of Theories
- On the topological aspects of the theory of represented spaces
