A topological view on algebraic computation models
From MaRDI portal
Publication:1679677
DOI10.1016/j.jco.2017.08.003OpenAlexW2407347945MaRDI QIDQ1679677
Publication date: 21 November 2017
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1602.08004
computable analysisWeihrauch reducibilityanalytic machineBSS-machineeffective DSTsolvability complexity index
Related Items
Comparing representations for function spaces in computable analysis, Reduction games, provability and compactness, Algebraic properties of the first-order part of a problem, THE DISCONTINUITY PROBLEM, On the complexity of learning programs, How constructive is constructing measures?, Completion of choice, Game characterizations and lower cones in the Weihrauch degrees, FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS, Game characterizations and lower cones in the Weihrauch degrees, Heuristic algorithms for recognition of some cubic hypersurfaces, A note on the diamond operator, SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE, WEIHRAUCH GOES BROUWERIAN, On the Weihrauch degree of the additive Ramsey theorem over the rationals, Unnamed Item, Weihrauch Complexity in Computable Analysis, Lawvere-Tierney topologies for computability theorists
Uses Software
Cites Work
- Unnamed Item
- 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
- New barriers in complexity theory: on the solvability complexity index and the towers of algorithms
- Computability of Julia sets
- A hierarchy below the halting problem for additive machines
- Recursively enumerable subsets of \(\mathbb{R}^{q}\) in two computing models Blum-Shub-Smale machine and Turing machine
- Algorithmic properties of polynomial rings
- Feasible real random access machines
- Equality is a jump
- Analytic machines
- On NP-completeness for linear machines
- Probabilistic computability and choice
- An explicit solution to Post's problem over the reals
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Real hypercomputation and continuity
- On uniform relationships between combinatorial problems
- On the Computational Content of the Brouwer Fixed Point Theorem
- Noncomputable functions in the Blum-Shub-Smale model
- On the (semi)lattices induced by continuous reducibilities
- On the Solvability Complexity Index, the 𝑛-pseudospectrum and approximations of spectra of operators
- Weihrauch degrees, omniscience principles and weak computability
- Effective Choice and Boundedness Principles in Computable Analysis
- Is the Mandelbrot set computable?
- Effective Borel measurability and reducibility of functions
- On notions of computability-theoretic reduction between Π21 principles
- Slicing the Truth
- Computable functionals
- On the definitions of computable real continuous functions
- On Σ‐definability without equality over the real numbers
- Computability of Analytic Functions with Analytic Machines
- A Singular Introduction to Commutative Algebra
- Computability of String Functions Over Algebraic Structures Armin Hemmerling
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On Relativizations of the P =? NP Question for Several Structures
- Revising Type-2 Computation and Degrees of Discontinuity
- The degree structure of Weihrauch-reducibility
- Levels of discontinuity, limit-computability, and jump operators
- Non-deterministic computation and the Jayne-Rogers Theorem
- On the topological aspects of the theory of represented spaces
- The P-DNP problem for infinite Abelian groups