Computation with Advice

Abstract

Computation with advice is suggested as generalization of both computation with discrete advice and Type-2 Nondeterminism. Several embodiments of the generic concept are discussed, and the close connection to Weihrauch reducibility is pointed out. As a novel concept, computability with random advice is studied; which corresponds to correct solutions being guessable with positive probability. In the framework of computation with advice, it is possible to define computational complexity for certain concepts of hypercomputation. Finally, some examples are given which illuminate the interplay of uniform and non-uniform techniques in order to investigate both computability with advice and the Weihrauch lattice.

References in corpus (4)

• Closed Choice and a Uniform Low Basis Theorem
• Real Hypercomputation and Continuity
• Revising Type-2 Computation and Degrees of Discontinuity
• Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability

Cited by in corpus (10)

• On the algebraic structure of Weihrauch degrees
• Probabilistic Computability and Choice
• Non-deterministic computation and the Jayne-Rogers Theorem
• Finite choice, convex choice and finding roots
• Many-one reductions and the category of multivalued functions
• On the topological aspects of the theory of represented spaces
• The Vitali Covering Theorem in the Weihrauch Lattice
• Convex choice, finite choice and sorting
• Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism
• The Weihrauch degree of finding Nash equilibria in multiplayer games