Many-one reductions and the category of multivalued functions

DOI10.1017/S0960129515000262zbMath1423.03157arXiv1102.3151MaRDI QIDQ2973252

Arno Pauly

Publication date: 3 April 2017

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Special categories (18B99) Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78)

Related Items

Unnamed Item, Borel-Piecewise Continuous Reducibility for Uniformization Problems, On the algebraic structure of Weihrauch degrees, Game characterizations and lower cones in the Weihrauch degrees, Weihrauch Complexity in Computable Analysis, Lawvere-Tierney topologies for computability theorists

Cites Work

• 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
• How incomputable is the separable Hahn-Banach theorem?
• Introduction to Turing categories
• How easy is local search?
• Categories of partial maps
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Restriction categories II: Partial map classification
• Probabilistic computability and choice
• Restriction categories as enriched categories
• Parametrized complexity theory.
• On uniform relationships between combinatorial problems
• On the Computational Content of the Brouwer Fixed Point Theorem
• Multi-valued Functions in Computability Theory
• Relative computability and uniform continuity of relations
• Complexity Theory for Operators in Analysis
• 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
• A Deterministic Subexponential Algorithm for Solving Parity Games
• The complexity of pure Nash equilibria
• Dominical categories: recursion theory without elements
• On the Structure of Polynomial Time Reducibility
• The Complexity of Decision Versus Search
• On the algebraic structure of Weihrauch degrees
• The degree structure of Weihrauch-reducibility
• Reducibility among Combinatorial Problems
• A dialectica-like model of linear logic
• Function Spaces for Second-Order Polynomial Time
• A minimal pair of recursively enumerable degrees
• On the topological aspects of the theory of represented spaces
• Restriction categories III: colimits, partial limits and extensivity
• Restriction categories. I: Categories of partial maps