Many-one reductions and the category of multivalued functions
From MaRDI portal
Publication:2973252
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4210141 (Why is no real title available?)
- scientific article; zbMATH DE number 3898875 (Why is no real title available?)
- scientific article; zbMATH DE number 4037840 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- scientific article; zbMATH DE number 786487 (Why is no real title available?)
- scientific article; zbMATH DE number 7311152 (Why is no real title available?)
- scientific article; zbMATH DE number 6783433 (Why is no real title available?)
- A Deterministic Subexponential Algorithm for Solving Parity Games
- A dialectica-like model of linear logic
- A minimal pair of recursively enumerable degrees
- Categories of partial maps
- Closed choice and a uniform low basis theorem
- Complexity theory for operators in analysis
- Dominical categories: recursion theory without elements
- Effective Choice and Boundedness Principles in Computable Analysis
- Function spaces for second-order polynomial time
- How easy is local search?
- How incomputable is finding Nash equilibria?
- How incomputable is the separable Hahn-Banach theorem?
- Introduction to Turing categories
- Multi-valued functions in computability theory
- On the (semi)lattices induced by continuous reducibilities
- On the Structure of Polynomial Time Reducibility
- On the algebraic structure of Weihrauch degrees
- On the complexity of the parity argument and other inefficient proofs of existence
- On the computational content of the Brouwer fixed point theorem
- On the topological aspects of the theory of represented spaces
- On uniform relationships between combinatorial problems
- Parametrized complexity theory.
- Probabilistic computability and choice
- Reducibility among combinatorial problems
- Relative computability and uniform continuity of relations
- Restriction categories II: Partial map classification
- Restriction categories III: colimits, partial limits and extensivity
- Restriction categories as enriched categories
- Restriction categories. I: Categories of partial maps
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- The Complexity of Decision Versus Search
- The complexity of pure Nash equilibria
- The degree structure of Weihrauch-reducibility
- The relative complexity of NP search problems
- Weihrauch degrees, omniscience principles and weak computability
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
- Multi-valued functions in computability theory
- On the algebraic structure of Weihrauch degrees
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)
