On the public citation graph

On genuinely time bounded computations

https://doi.org/10.1007/bfb0028969
0 signed · 36 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-07805-3openalex-snapshot
Komplexität von Entscheidungsproblemen Ein Seminar
inferredcites →https://doi.org/10.1007/3-540-07854-1_185openalex-snapshot
A lower bound of 1/2n2 on linear search programs for the knapsack problem
inferredcites →https://doi.org/10.1007/3-540-09510-1_42openalex-snapshot
On the power of random access machines
inferredcites →https://doi.org/10.1007/bf00571464openalex-snapshot
Berechnung und Programm. II
inferredcites →https://doi.org/10.1007/bfb0029630openalex-snapshot
On the complexity of genuinely polynomial computation
inferredcites →https://doi.org/10.1007/bfb0035829openalex-snapshot
On computations with integer division
inferredcites →https://doi.org/10.1016/0022-0000(78)90026-0openalex-snapshot
A lower bound of 12n2 on linear search programs for the Knapsack problem
inferredcites →https://doi.org/10.1016/0196-6774(82)90002-5openalex-snapshot
Lower bounds for algebraic decision trees
inferredcites →https://doi.org/10.1016/0304-3975(85)90079-9openalex-snapshot
Simulating probabilistic by deterministic algebraic computation trees
inferredcites →https://doi.org/10.1016/0890-5401(88)90031-4openalex-snapshot
On the limits of computations with the floor function
inferredcites →https://doi.org/10.1090/s0002-9939-1964-0161339-9openalex-snapshot
On the Betti Numbers of Real Varieties
inferredcites →https://doi.org/10.1109/sfcs.1979.13openalex-snapshot
Division is good
inferredcites →https://doi.org/10.1109/sfcs.1988.21955openalex-snapshot
On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines
inferredcites →https://doi.org/10.1137/0212022openalex-snapshot
Towards a Genuinely Polynomial Algorithm for Linear Programming
inferredcites →https://doi.org/10.1145/321724.321730openalex-snapshot
On the Optimality of Some Set Algorithms
inferredcites →https://doi.org/10.1145/4221.4250openalex-snapshot
Lower bounds for solving linear diophantine equations on random access machines
inferredcites →https://doi.org/10.1145/44483.44490openalex-snapshot
Fast algorithms for N -dimensional restrictions of hard problems
inferredcites →https://doi.org/10.1145/800057.808695openalex-snapshot
A new polynomial-time algorithm for linear programming
inferredcites →https://doi.org/10.1145/800061.808735openalex-snapshot
Lower bounds for algebraic computation trees
inferredcites →https://doi.org/10.1145/800125.804033openalex-snapshot
Elementary bounds for presburger arithmetic
inferredcites →https://doi.org/10.1145/828.322450openalex-snapshot
A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
inferredcites →https://doi.org/10.1287/opre.34.2.250openalex-snapshot
A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
inferredcites →https://doi.org/10.2307/2322374openalex-snapshot
Combinatorial Optimization: Algorithms and Complexity.

What points at this work

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

inferred← citeshttps://doi.org/10.1006/inco.1993.1057openalex-snapshot
Point Location in Arrangements of Hyperplanes
inferred← citeshttps://doi.org/10.1006/jcom.1995.1002openalex-snapshot
The Real Number Model in Numerical Analysis
inferred← citeshttps://doi.org/10.1007/3-540-57529-4_59openalex-snapshot
Recursiveness over the complex numbers is time-bounded
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_88openalex-snapshot
Lower bounds on algebraic random access machines
inferred← citeshttps://doi.org/10.1007/978-3-322-80139-5_2openalex-snapshot
Weitere Maschinenmodelle
inferred← citeshttps://doi.org/10.1007/bf01270397openalex-snapshot
Lower bounds for arithmetic networks
inferred← citeshttps://doi.org/10.1007/bf01990341openalex-snapshot
An efficient implicit data structure for relation testing and searching in partially ordered sets
inferred← citeshttps://doi.org/10.1007/bfb0029630openalex-snapshot
On the complexity of genuinely polynomial computation
inferred← citeshttps://doi.org/10.1016/0304-3975(90)90181-gopenalex-snapshot
Strong time bounds: Non-computable bounds and a hierarchy theorem
inferred← citeshttps://doi.org/10.1137/0220020openalex-snapshot
Lower Bounds for Computations with the Floor Operation
inferred← citeshttps://doi.org/10.1137/s0097539797329397openalex-snapshot
Topological Lower Bounds on Algebraic Random Access Machines
inferred← citeshttps://doi.org/10.1145/1162349.1162353openalex-snapshot
Backing up in singly linked lists
inferred← citeshttps://doi.org/10.1145/301250.301450openalex-snapshot
Backing up in singly linked lists
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.