Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-24T15:20:21.084Z Has data issue: false hasContentIssue false
  • English
  • Français

Many-one reductions and the category of multivalued functions

Published online by Cambridge University Press:  03 July 2015

ARNO PAULY
ARNO PAULY*
Affiliation:
Computer Laboratory, University of Cambridge Email: arno.pauly@cl.cam.ac.uk.
Get access Rights & Permissions [Opens in a new window]

Abstract

Multivalued 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 multivalued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multivalued 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 multivalued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multivalued functions.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Issue 3 , March 2017 , pp. 376 - 404
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ambos-Spies, K. (1987). Minimal pairs for polynomial time reducibilities. In: Computation Theory and Logic. Springer Lecture Notes in Computer Science 270 1–13.Google Scholar
Bauer, A. (1998). Topology and computability. Thesis proposal (for Bauer (2000)), Carniege Mellon University.Google Scholar
Bauer, A. (2000). The Realizability Approach to Computable Analysis and Topology. PhD thesis, Carnegie Mellon University.Google Scholar
Bauer, A. (2004). Realizability as the connection between computable and constructive mathematics. Tutorial at CCA 2004 (notes).Google Scholar
Beame, P., Cook, S., Edmonds, J., Impagliazzo, R. and Pitassi, T. (1998). The relative complexity of NP search problems. Journal of Computer and System Science 57 3–19.CrossRefGoogle Scholar
Bellare, M. and Goldwasser, S. (1994) The complexity of decision versus search. SIAM Journal on Computing 23 97–119.Google Scholar
Blass, A. (1995). Questions and answers – a category arising in linear logic, complexity theory, and set theory. In: Girard, J. Y., Lafont, Y., and Regnier, L. (eds.) Advances in Linear Logic, London Mathematical Society Lecture Note Series, Cambridge University Press, volume 222, 61–81. arXiv:math/9309208.CrossRefGoogle Scholar
Borodin, A., Constable, R. L. and Hopcroft, J. E. (1969). Dense and non-dense families of complexity classes. In: Proceedings of the 10th Annual Symposium on Switching and Automata Theory 7–19.Google Scholar
Brattka, V., de Brecht, M. and Pauly, A. (2012a). Closed choice and a uniform low basis theorem. Annals of Pure and Applied Logic 163 (8) 968–1008.Google Scholar
Brattka, V. and Gherardi, G. (2011a). Effective choice and boundedness principles in computable analysis. Bulletin of Symbolic Logic 1 73–117 arXiv:0905.4685.Google Scholar
Brattka, V. and Gherardi, G. (2011b). Weihrauch degrees, omniscience principles and weak computability. Journal of Symbolic Logic 76 143–176 arXiv:0905.4679.Google Scholar
Brattka, V., Gherardi, G. and Hölzl, R. (2015). Probabilistic computability and choice. Information and Computation 242, 249–286.Google Scholar
Brattka, V., Gherardi, G. and Marcone, A. (2012b). The Bolzano-Weierstrass Theorem is the jump of Weak König's Lemma. Annals of Pure and Applied Logic 163 (6) 623–625 also arXiv:1101.0792.CrossRefGoogle Scholar
Brattka, V. and Hertling, P. (1994). Continuity and computability of relations. Informatik Berichte 164, FernUniversität Hagen.Google Scholar
Brattka, V., LeRoux, S. and Pauly, A. (2012c). On the computational content of the Brouwer fixed point theorem. In: Barry Cooper, S., Dawar, A. and Löwe, B. (eds.) How the World Computes, Lecture Notes in Computer Science volume 7318, 56–67.Google Scholar
Brattka, V. and Pauly, A. On the algebraic structure of Weihrauch degrees. forthcoming.Google Scholar
Brattka, V. and Pauly, A. (2010). Computation with advice. Electronic Proceedings in Theoretical Computer Science 24 CCA 2010.CrossRefGoogle Scholar
Chen, X. and Deng, X. (2005). Settling the complexity of 2-player Nash-equilibrium. Technical Report 134, Electronic Colloquium on Computational Complexity.Google Scholar
Cockett, J. R. B. and Hofstra, P. J. W. (2008). Introduction to Turing categories. Annals of Pure and Applied Logic 156 (2–3) 183–209.Google Scholar
Cockett, J. R. B. and Lack, S. (2002). Restriction categories I: Categories of partial maps. Theoretical Computer Science 270 (1–2) 223–259.Google Scholar
Cockett, J. R. B. and Lack, S. (2003). Restriction categories II: Partial map classification. Theoretical Computer Science 294 (1–2) 61–102. Category Theory and Computer Science.Google Scholar
Cockett, R. and Garner, R. (2014). Restriction Categories As Enriched Categories. Theoretical Computer Science, 523, 37–55.CrossRefGoogle Scholar
Cockett, R. and Lack, S. (2007). Restriction categories III: Colimits, partial limits and extensivity. Mathematical Structures in Computer Science 17 775–817.Google Scholar
dePaiva, V. (1989). A Dialectica-like model of linear logic. In: Pitt, D. et al. (ed.) Categories in Computer Science and Logic. Springer Lecture Notes in Computer Science 389.Google Scholar
Daskalakis, C. and Papadimitriou, C. (2011). Continuous local search. In: Proceedings of SODA 790–804.Google Scholar
DiPaola, R. and Heller, A. (1987). Dominical categories: Recursion theory without elements. Journal of Symbolic Logic 52 594–635.Google Scholar
Dorais, F. G., Dzhafarov, D. D., Hirst, J. L., Mileti, J. R. and Shafer, P. On uniform relationships between combinatorial problems. Transactions of the AMS, to appear. arXiv 1212.0157.Google Scholar
Downey, R. and Fellows, M. (1999). Parameterized Complexity, Springer.Google Scholar
Etessami, K. and Yannakakis, M. (2007). On the complexity of Nash equilibria and other fixed points (extended abstract). In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science 113–123.Google Scholar
Fabrikant, A., Papadimitriou, C. and Talwar, K. (2004). The complexity of pure Nash equilibria. In: STOC '04: Proceedings of the 36th Annual ACM Symposium on Theory of Computing 604–612.Google Scholar
Flum, J. and Grohe, M. (2006). Parameterized Complexity Theory, Springer.Google Scholar
Gherardi, G. and Marcone, A. (2009). How incomputable is the separable Hahn-Banach theorem. Notre Dame Journal of Formal Logic 50 (4) 393–425.Google Scholar
Gottlob, G. (2005). Computing cores for data exchange: New algorithms and practical solutions. In: PODS 148–159.Google Scholar
Higuchi, K. and Pauly, A. (2013). The degree-structure of Weihrauch-reducibility. Logical Methods in Computer Science 9 (2).Google Scholar
Hoyrup, M., Rojas, C. and Weihrauch, K. (2012). Computability of the Radon-Nikodym derivative. Computability 1 (1) 3–13.Google Scholar
Johnson, D. S., Papadimtriou, C. H. and Yannakakis, M. (1988). How easy is local search. Journal of Computer and System Sciences 37 (1) 79–100.Google Scholar
Jurdzinski, M., Paterson, M. and Zwick, U. (2008). A deterministic subexponential algorithm for solving parity games. SIAM J. Comput. 38 (4) 1519–1532.Google Scholar
Karp, R. M. (1972). Reducibility among combinatorial problems. In: Miller, R. E. and Thatcher, J. W. (eds.) Complexity of Computer Computations, Plenum 85–103.Google Scholar
Kawamura, A. and Cook, S. (2012). Complexity theory for operators in analysis. ACM Transactions on Computation Theory 4 (2).Google Scholar
Kawamura, A. and Pauly, A. (2014a). Function spaces for second-order polynomial time. In: Beckmann, A., Csuhaj-Varjú, E. and Meer, K. (eds.) Language, Life, Limits, Lecture Notes in Computer Science volume 8493, 245–254.Google Scholar
Kawamura, A. and Pauly, A. (2014b). Function spaces for second-order polynomial time. arXiv 1401.2861.Google Scholar
Kozen, D. (1990). On Kleene algebras and closed semirings. In. Proceedings of the Mathematical Foundations of Computer Science. Springer Lecture Notes in Computer Science 452.Google Scholar
Ladner, R. E. (1975). On the structure of polynomial time reducibility. Journal of the ACM 22 (1) 155–171.Google Scholar
Longo, G. and Moggi, E. (1984). Cartesian closed categories of enumerations and effective type structures. In: Khan, P. and MacQueen, , (eds.) Symposium on Semantics of Data Types. Springer Lecture Notes in Computer Science 173.Google Scholar
Medvedev, Y. T. (1955). Degrees of difficulty of mass problems. Doklady Akademii Nauk SSSR 104 501–504.Google Scholar
Papadimitriou, C. H. (1994). On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and Systems Science 48 (3) 498–532.Google Scholar
Pauly, A. (2010a). How incomputable is finding Nash equilibria. Journal of Universal Computer Science 16 (18) 2686–2710.Google Scholar
Pauly, A. (2010b). On the (semi)lattices induced by continuous reducibilities. Mathematical Logic Quarterly 56 (5) 488–502.Google Scholar
Pauly, A. (2012a). Multi-valued functions in computability theory. In: Cooper, S., Dawar, A. and Löwe, B. (eds.) How the World Computes, Lecture Notes in Computer Science volume 7318, 571–580.CrossRefGoogle Scholar
Pauly, A. (2012b). On the topological aspects of the theory of represented spaces. http://arxiv.org/abs/1204.3763.Google Scholar
Pauly, A. and Ziegler, M. (2013). Relative computability and uniform continuity of relations. Journal of Logic and Analysis 5 1–39.Google Scholar
Robinson, E. and Rosolini, G. (1988). Categories of partial maps. Information and Computation 79 (2) 95–130.Google Scholar
Weihrauch, K. (July 1992a). The degrees of discontinuity of some translators between representations of the real numbers. Informatik Berichte 129, FernUniversität Hagen, Hagen.Google Scholar
Weihrauch, K. (September 1992b). The TTE-interpretation of three hierarchies of omniscience principles. Informatik Berichte 130, FernUniversität Hagen, Hagen.Google Scholar
Weihrauch, K. (2000). Computable Analysis, Springer-Verlag.Google Scholar
Yates, C. E. M. (1966). A minimal pair of recursively enumerable degrees. The Journal of Symbolic Logic 31 (2) 159–168.CrossRefGoogle Scholar
Yoshimura, K. (2014). From Weihrauch lattice to logic: Part I. unpublished notes.Google Scholar