Many-one reductions and the category of multivalued functions
From MaRDI portal
Publication:2973252
DOI10.1017/S0960129515000262zbMATH Open1423.03157arXiv1102.3151MaRDI QIDQ2973252FDOQ2973252
Authors: Arno Pauly 
Publication date: 3 April 2017
Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)
Abstract: Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degrees). A more general understanding is possible, if the category-theoretic properties of multi-valued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multi-valued functions form a distributive lattice under very general conditions, regardless of the actual reducibility notions used (e.g. Cook, Karp, Weihrauch). Beyond this, an abundance of open questions arises. Some classic results for reductions between functions carry over to multi-valued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multi-valued functions.
Full work available at URL: https://arxiv.org/abs/1102.3151
Recommendations
Computation over the reals, computable analysis (03D78) Special categories (18B99) Other degrees and reducibilities in computability and recursion theory (03D30)
Cites Work
- Reducibility among combinatorial problems
- Parametrized complexity theory.
- On the Structure of Polynomial Time Reducibility
- Title not available (Why is that?)
- Title not available (Why is that?)
- How easy is local search?
- On the complexity of the parity argument and other inefficient proofs of existence
- Dominical categories: recursion theory without elements
- Restriction categories. I: Categories of partial maps
- Introduction to Turing categories
- The complexity of pure Nash equilibria
- Title not available (Why is that?)
- The relative complexity of NP search problems
- How incomputable is finding Nash equilibria?
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Title not available (Why is that?)
- Weihrauch degrees, omniscience principles and weak computability
- On the (semi)lattices induced by continuous reducibilities
- Effective Choice and Boundedness Principles in Computable Analysis
- 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?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relative computability and uniform continuity of relations
- Function spaces for second-order polynomial time
- On uniform relationships between combinatorial problems
- Categories of partial maps
- Restriction categories II: Partial map classification
- Restriction categories as enriched categories
- Restriction categories III: colimits, partial limits and extensivity
- The Complexity of Decision Versus Search
- On the computational content of the Brouwer fixed point theorem
- A minimal pair of recursively enumerable degrees
- Title not available (Why is that?)
- Title not available (Why is that?)
- A dialectica-like model of linear logic
- The degree structure of Weihrauch-reducibility
- Probabilistic computability and choice
- On the algebraic structure of Weihrauch degrees
- On the topological aspects of the theory of represented spaces
- Complexity theory for operators in analysis
- Multi-valued functions in computability theory
Cited In (7)
- Lawvere-Tierney topologies for computability theorists
- Computable analysis and notions of continuity in \textsc{Coq}
- Game characterizations and lower cones in the Weihrauch degrees
- Borel-piecewise continuous reducibility for uniformization problems
- Weihrauch Complexity in Computable Analysis
- On the algebraic structure of Weihrauch degrees
- Multi-valued functions in computability theory
This page was built for publication: Many-one reductions and the category of multivalued functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2973252)
