On the public citation graph

On the definitions of some complexity classes of real numbers

https://doi.org/10.1007/bf01744572
0 signed · 85 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-08860-1_6openalex-snapshot
Relationship between density and deterministic complexity of MP-complete languages
inferredcites →https://doi.org/10.1007/978-3-0348-9259-9_2openalex-snapshot
Nicht Konstruktiv Beweisbare Sätze der Analysis
inferredcites →https://doi.org/10.1007/bf01744288openalex-snapshot
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
inferredcites →https://doi.org/10.1016/0022-0000(81)90068-4openalex-snapshot
Some observations on NP real numbers and P-selective sets
inferredcites →https://doi.org/10.1016/0022-0000(82)90053-8openalex-snapshot
The maximum value problem and NP real numbers
inferredcites →https://doi.org/10.1016/0304-3975(75)90016-xopenalex-snapshot
A comparison of polynomial time reducibilities
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/s0019-9958(74)90473-2openalex-snapshot
Tally languages and complexity classes
inferredcites →https://doi.org/10.1016/s0049-237x(09)70267-8openalex-snapshot
On computable sequences
inferredcites →https://doi.org/10.1016/s0049-237x(09)70270-8openalex-snapshot
On Various Degrees of Constructivism
inferredcites →https://doi.org/10.1016/s0304-3975(82)80003-0openalex-snapshot
Computational complexity of real functions
inferredcites →https://doi.org/10.1090/s0002-9939-1954-0063328-5openalex-snapshot
Recursive Real Numbers
inferredcites →https://doi.org/10.1093/comjnl/12.1.28openalex-snapshot
Theory of Recursive Functions and Effective Computability
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1112/plms/s2-42.1.230openalex-snapshot
On Computable Numbers, with an Application to the Entscheidungsproblem
inferredcites →https://doi.org/10.1145/322047.322061openalex-snapshot
Separating Nondeterministic Time Complexity Classes
inferredcites →https://doi.org/10.2307/2267043openalex-snapshot
Nicht konstruktiv beweisbare Sätze der Analysis
inferredcites →https://doi.org/10.2307/2316720openalex-snapshot
Theory of Recursive Functions and Effective Computability.
inferredcites →https://doi.org/10.4064/fm-44-1-37-51openalex-snapshot
On computable sequences

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/jcom.2000.0561openalex-snapshot
Weakly Computable Real Numbers
inferred← citeshttps://doi.org/10.1006/jcss.1995.1014openalex-snapshot
On the NP-Isomorphism Problem with Respect to Random Instances
inferred← citeshttps://doi.org/10.1007/11537311_36openalex-snapshot
Average-Case Non-approximability of Optimisation Problems
inferred← citeshttps://doi.org/10.1007/11780342_60openalex-snapshot
A Computability Theory of Real Numbers
inferred← citeshttps://doi.org/10.1007/3-540-16486-3_85openalex-snapshot
The complexity of sparse sets in P
inferred← citeshttps://doi.org/10.1007/3-540-16761-7_49openalex-snapshot
Characterizations of PUNC and precomputation
inferred← citeshttps://doi.org/10.1007/3-540-44683-4_28openalex-snapshot
Randomness and Reductibility
inferred← citeshttps://doi.org/10.1007/3-540-44693-1_17openalex-snapshot
Randomness, Computability, and Density
inferred← citeshttps://doi.org/10.1007/3-540-60922-9_28openalex-snapshot
Fine separation of average time complexity classes
inferred← citeshttps://doi.org/10.1007/3-540-63577-7_33openalex-snapshot
Inferability of recursive real-valued functions
inferred← citeshttps://doi.org/10.1007/978-1-4612-1872-2_12openalex-snapshot
Average-Case Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-1-4613-3394-4_15openalex-snapshot
Average-Case Intractable NP Problems
inferred← citeshttps://doi.org/10.1007/978-3-030-41672-0_1openalex-snapshot
In Memoriam: Ker-I Ko (1950–2018)
inferred← citeshttps://doi.org/10.1007/978-3-030-51466-2_7openalex-snapshot
On the Complexity of Conversion Between Classic Real Number Representations
inferred← citeshttps://doi.org/10.1007/978-3-030-80049-9_23openalex-snapshot
Dedekind Cuts and Long Strings of Zeros in Base Expansions
inferred← citeshttps://doi.org/10.1007/978-3-032-31348-5_21openalex-snapshot
Closure Properties of Left NP Real Numbers and NP Real Functions
inferred← citeshttps://doi.org/10.1007/978-3-319-94418-0_20openalex-snapshot
On General Sum Approximations of Irrational Numbers
inferred← citeshttps://doi.org/10.1007/978-3-540-24738-8_16openalex-snapshot
Using PVS to Validate the Inverse Trigonometric Functions of an Exact Arithmetic
inferred← citeshttps://doi.org/10.1007/bfb0035750openalex-snapshot
Lower bounds for the low hierarchy
inferred← citeshttps://doi.org/10.1007/bfb0055831openalex-snapshot
A finite hierarchy of the recursively enumerable real numbers
inferred← citeshttps://doi.org/10.1007/pl00009267openalex-snapshot
Reductions Do Not Preserve Fast Convergence Rates in Average Time
inferred← citeshttps://doi.org/10.1016/0020-0190(84)90078-4openalex-snapshot
Probabilistics Turing machines and recursively enumerable Dedekind cuts
inferred← citeshttps://doi.org/10.1016/0022-0000(81)90068-4openalex-snapshot
Some observations on NP real numbers and P-selective sets
inferred← citeshttps://doi.org/10.1016/0022-0000(82)90053-8openalex-snapshot
The maximum value problem and NP real numbers
inferred← citeshttps://doi.org/10.1016/0022-0000(91)90007-ropenalex-snapshot
Average case completeness
inferred← citeshttps://doi.org/10.1016/0168-0072(86)90005-9openalex-snapshot
Approximation to measurable functions and its relation to probabilistic computation
inferred← citeshttps://doi.org/10.1016/0168-0072(87)90065-0openalex-snapshot
Representations of the real numbers and of the open subsets of the set of real numbers
inferred← citeshttps://doi.org/10.1016/0168-0072(90)90052-4openalex-snapshot
Real numbers, continued fractions and complexity classes
inferred← citeshttps://doi.org/10.1016/0304-3975(84)90129-4openalex-snapshot
Reducibilities on real numbers
inferred← citeshttps://doi.org/10.1016/0304-3975(86)90154-4openalex-snapshot
On the continued fraction representation of computable real numbers
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90080-lopenalex-snapshot
Représentations des nombres réels par développements en base entière et complexité
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90275-7openalex-snapshot
Complexité du calcul du développement d'un nombre réel en fractions continues
inferred← citeshttps://doi.org/10.1016/0885-064x(86)90014-2openalex-snapshot
On the computational complexity of best Chebyshev approximations
inferred← citeshttps://doi.org/10.1016/0885-064x(92)90023-5openalex-snapshot
A note on best fractions of a computable real number
inferred← citeshttps://doi.org/10.1016/0890-5401(88)90044-2openalex-snapshot
Polynomial terse sets
inferred← citeshttps://doi.org/10.1016/j.apal.2020.102893openalex-snapshot
Computable irrational numbers with representations of surprising complexity
inferred← citeshttps://doi.org/10.1016/j.entcs.2006.08.018openalex-snapshot
Primitive Recursiveness of Real Numbers under Different Representations
inferred← citeshttps://doi.org/10.1016/j.jcss.2003.07.004openalex-snapshot
Randomness and reducibility
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.11.016openalex-snapshot
The computational complexity of distance functions of two-dimensional domains
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.10.004openalex-snapshot
On logarithmic-space computable real numbers
inferred← citeshttps://doi.org/10.1016/s0019-9958(82)80084-3openalex-snapshot
Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
inferred← citeshttps://doi.org/10.1016/s0049-237x(98)80013-xopenalex-snapshot
Chapter 12 A bibliography of recursive analysis and recursive topology
inferred← citeshttps://doi.org/10.1016/s0049-237x(98)80052-9openalex-snapshot
Chapter 19 Polynomial-time computability in analysis
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00226-8openalex-snapshot
Using PVS to validate the algorithms of an exact arithmetic
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00139-5openalex-snapshot
Espaces métriques rationnellement présentés et complexité, le cas de l'espace des fonctions réelles uniformément continues sur un intervalle compact
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00295-9openalex-snapshot
Complete distributional problems, hard languages, and resource-bounded measure
inferred← citeshttps://doi.org/10.1051/ita/1987210201751openalex-snapshot
On the complexity of computable real sequences
inferred← citeshttps://doi.org/10.1109/ccc.1998.694604openalex-snapshot
Probabilistic martingales and BPTIME classes
inferred← citeshttps://doi.org/10.1109/sct.1992.215406openalex-snapshot
On average P vs. average NP
inferred← citeshttps://doi.org/10.1109/sct.1993.336540openalex-snapshot
Isomorphisms of NP complete problems on random instances
inferred← citeshttps://doi.org/10.1109/sct.1994.315803openalex-snapshot
Test instance generation for promised NP search problems
inferred← citeshttps://doi.org/10.1109/sfcs.1987.14openalex-snapshot
Complete and incomplete randomized NP problems
inferred← citeshttps://doi.org/10.1137/s0097539700376937openalex-snapshot
Randomness, Computability, and Density
inferred← citeshttps://doi.org/10.1137/s0097539796311715openalex-snapshot
Fine Separation of Average-Time Complexity Classes
inferred← citeshttps://doi.org/10.1137/s0097539797332263openalex-snapshot
Distributional Word Problem for Groups
inferred← citeshttps://doi.org/10.1145/147508.147546openalex-snapshot
Lower bounds for the low hierarchy
inferred← citeshttps://doi.org/10.1145/3319627.3319641openalex-snapshot
In Memoriam
inferred← citeshttps://doi.org/10.1177/22113568261468518openalex-snapshot
Avoiding the subrecursive cone of Cauchy sequences
inferred← citeshttps://doi.org/10.1287/moor.2022.1272openalex-snapshot
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
inferred← citeshttps://doi.org/10.2197/ipsjjip.25.494openalex-snapshot
Speeding up Exact Real Arithmetic on Fast Binary Cauchy Sequences by Using Memoization Based on Quantized Precision
inferred← citeshttps://doi.org/10.3233/com-160063openalex-snapshot
On subrecursive representability of irrational numbers
inferred← citeshttps://doi.org/10.3233/com-170081openalex-snapshot
On subrecursive representability of irrational numbers, part II
inferred← citeshttps://doi.org/10.3233/com-220407openalex-snapshot
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs
inferred← citeshttps://doi.org/10.3233/com-230469openalex-snapshot
Interplay between insertion of zeros and the complexity of Dedekind cuts
inferred← citeshttps://doi.org/10.48550/arxiv.1804.05330openalex-snapshot
Subrecursive Approximations of Irrational Numbers by Variable Base Sums
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0608067openalex-snapshot
On Polynomial Time Computable Numbers
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.