Time bounded random access machines
From MaRDI portal
Publication:1844708
DOI10.1016/S0022-0000(73)80029-7zbMath0284.68038MaRDI QIDQ1844708
Robert A. Reckhow, Stephen A. Cook
Publication date: 1973
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)
Related Items
Invariance properties of RAMs and linear time, Universal quantifiers and time complexity of random access machines, Unit-cost pointers versus logarithmic-cost addresses, A theory of strict P-completeness, Unnamed Item, Array processing machines: an abstract model, Lower bounds to processor-time tradeoffs under bounded-speed message propagation, Tables should be sorted (on random access machines), Optimal length resolution refutations of difference constraint systems, Secure Multiparty RAM Computation in Constant Rounds, The problem of space invariance for sequential machines, Squeezing Feasibility, An application of the translational method, Unnamed Item, Smoothing the Gap Between NP and ER, Unnamed Item, Complexity theory of parallel time and hardware, Space measures for storage modification machines, Adaptively secure computation for RAM programs, The complexity of on-line simulations between multidimensional turing machines and random access machines, On the generic solution to \(P(X)\cong X\) in distributive categories, Programs=data=first-class citizens in a computational world, From Turing machines to computer viruses, Projective plan and Möbius band obstructions, A computation model with automatic functions and relations as primitive operations, Dynamic Random-Access Stored-Program Machine for Runtime Code Modification, Obstructions for the Disk and the Cylinder Embedding Extension Problems, On time hierarchies, A characterization of time complexity by simple loop programs, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Inexactness and a future of computing, 3-party distributed ORAM from oblivious set membership, Linkless and flat embeddings in 3-space, Programmable and parallel water computing, Parameterized random complexity, Classifying the computational complexity of problems, Strong time bounds: Non-computable bounds and a hierarchy theorem, Improved bounds for finger search on a RAM, Random access machines with multi-dimensional memories, A survey of state vectors, Theorems on the time hierarchy for random access machines, On the complexity of the closed fragment of Japaridze's provability logic, On quasilinear-time complexity theory, The complexity types of computable sets, Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time, Multiplication, division, and shift instructions in parallel random access machines, Finding read-once resolution refutations in systems of 2CNF clauses, From imperative to rule-based graph programs, Models of quantum computation and quantum programming languages, On the complexity of the correctness problem for non-zeroness test instruction sequences, Non-deterministic structures of computation, 2-restricted extensions of partial embeddings of graphs, Parallel \(\mathcal H\)-matrix arithmetics on shared memory systems, Nonexistence of program optimizers in several abstract settings, A characterization of the power of vector machines, The polynomial-time hierarchy, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs, Computational complexity of multitape Turing machines and random access machines, Dynamic interpolation search revisited, Almost-everywhere complexity hierarchies for nondeterministic time, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, Sorting, linear time and the satisfiability problem, Polynomial size linear programs for problems in \textsc{P}, A theory of strict P-completeness, Quantum random access stored-program machines, Upper bounds for sorting integers on random access machines, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, A Process Algebra for Reasoning About Quantum Security, Notes on the complexity of sorting in abstract machines, Parallel random access machines with powerful instruction sets
Uses Software
Cites Work
