On the Computational Complexity of Algorithms
From MaRDI portal
Publication:5339741
DOI10.2307/1994208zbMath0131.15404OpenAlexW4239242491WikidataQ55879296 ScholiaQ55879296MaRDI QIDQ5339741
Richard E. Stearns, Juris Hartmanis
Publication date: 1965
Full work available at URL: https://doi.org/10.2307/1994208
Related Items
The theory of languages, Counter machines and counter languages, Hartmanis-Stearns Conjecture on Real Time and Transcendence, A Short Introduction to Implicit Computational Complexity, Real-time solutions of the origin-crossing problem, Universal Sleptsov net, Quasi-realtime languages, [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung], The theory of languages, Squeezing Feasibility, An application of the translational method, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Komplexität von Algorithmen mit Anwendung auf die Analysis, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Computational complexity of random access stored program machines, Programs=data=first-class citizens in a computational world, A Turing test for free will, On restricted turing computability, A unified approach to the definition of random sequences, Multi-stack-counter languages, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, Expressing computational complexity in constructive type theory, Unnamed Item, Indistinguishability and First-Order Logic, Rankable distributions do not provide harder instances than uniform distributions, Dimension and the structure of complexity classes, Effective guessing has unlikely consequences, Computability and Complexity in Self-assembly, Reductions and convergence rates of average time, On the irrationality measure of the Thue–Morse constant, On the Minimum Computation Time of Functions, Uniform tag sequences, Number Theoretic Aspects of Regular Sequences, Dynamic Modeling in Inductive Inference, On the cutting edge of relativization: The resource bounded injury method, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, A Time Hierarchy Theorem for the LOCAL Model, A note on the complexity of program evaluation, Relationships between pushdown automata with counters and complexity classes, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Towards separating nondeterminism from determinism, Lower bounds for multiplayer noncooperative games of incomplete information, The computational power of parsing expression grammars, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited, Efficient learning algorithms yield circuit lower bounds, Unnamed Item, Multitape one-way nonwriting automata, Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\), Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, Notes on Levin’s Theory of Average-Case Complexity, Complexity Theory Basics: NP and NL, Deciding According to the Shortest Computations, Alternating time versus deterministic time: A separation, Time-restricted sequence generation, A Hierarchy of Fast Reversible Turing Machines, Time- and tape-bounded Turing acceptors and AFLs, $$P\mathop{ =}\limits^{?}NP$$, Circuit lower bounds from NP-hardness of MCSP under turing reductions, The enumerability and invariance of complexity classes, Real-time computations with restricted nondeterminism, Subrecursive programming languages. II. On program size, k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines), Complexity problems in real time languages, Tabulator-Turingmaschine und Komplexität. (Tabulator Turing machine and complexity), Time-bounded grammars and their languages, On non-determinacy in simple computing devices, Writing stack acceptors, The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic, Production en temps réel et complexité de structure de suites infinies, Unnamed Item, Tape-reversal bounded Turing machine computations, Berechnungen in partiellen Algebren endlichen Typs, Real-time language recognition by one-dimensional cellular automata, Almost global problems in the LOCAL model, The Developments of the Concept of Machine Computability from 1936 to the 1960s, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Veridical data science, The complexity of type inference for higher-order typed lambda calculi, COMPOSITIONALITY, COMPUTABILITY, AND COMPLEXITY, Implicit computation complexity in higher-order programming languages, On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), On the complexity of algebraic numbers, On the structure of one-tape nondeterministic Turing machine time hierarchy, Reverse complexity, Generality's price: Inescapable deficiencies in machine-learned programs, Continued fractions and transcendental numbers, Efficient algorithms for membership in Boolean hierarchies of regular languages, Some remarks on real numbers induced by first-order spectra, Time hierarchies for cryptographic function inversion with advice, Computational complexity of functions, Computing equilibria: a computational complexity perspective, Semi-Galois categories. II: An arithmetic analogue of Christol's theorem, Robust real-time computing with chemical reaction networks, Fractal dimension of assemblies in the abstract tile assembly model, Tape versus queue and stacks: The lower bounds, Separating classes in the exponential-time hierarchy from classes in PH, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Real-time computability of real numbers by chemical reaction networks, Accepting networks of splicing processors: complexity results, A note on the best-case complexity, Completeness proofs for propositional logic with polynomial-time connectives, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, On relationships between complexity classes of Turing machines, Learning secrets interactively. Dynamic modeling in inductive inference, On transformations of programs, Deterministic multitape automata computations, Indirect addressing and the time relationships of some models of sequential computation, On time versus space. II, Complexity of algorithms and computations, Complexity results for classes of quantificational formulas, Complexity-theoretic algebra. II: Boolean algebras, Unprovability of theorems of complexity theory in weak number theories, Some results on relativized deterministic and nondeterministic time hierarchies, Parametrization over inductive relations of a bounded number of variables, Simulations among multidimensional Turing machines, When is arithmetic possible?, On uniformity and circuit lower bounds, An analysis of fixed-point queries on binary trees, On the complexity of the Leibniz hierarchy, Almost global problems in the LOCAL model, Weak completeness in \(\text{E}\) and \(\text{E}_{2}\), The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Multihead two-way probabilistic finite automata, Oracles for structural properties: The isomorphism problem and public-key cryptography, Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces, Multiplication, division, and shift instructions in parallel random access machines, On the computational power of networks of polarized evolutionary processors, On the power of several queues, Linear speed-up does not hold on Turing machines with tree storages, Diagonalization, uniformity, and fixed-point theorems, A speed-up theorem without tape compression, Computability and complexity in self-assembly, Small universal accepting hybrid networks of evolutionary processors, On the size complexity of hybrid networks of evolutionary processors, A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors, Hierarchies of Turing machines with restricted tape alphabet size, Augmented loop languages and classes of computable functions, On the complexity of algebraic numbers. II: Continued fractions, Translational lemmas, polynomial time, and \((\log n)^j\)-space, Polynomial and abstract subrecursive classes, Comparing complexity classes, Minimal pairs of polynomial degrees with subexponential complexity, Complexity results for deciding networks of evolutionary processors, Incremental delay enumeration: space and time, Relative complexity of checking and evaluating, Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem, The strong exponential hierarchy collapses, Mahler's method, ``V-tape, a virtual memory oriented data type, and its resource requirements, Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, \(\omega\)-computations on Turing machines, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, Palindrome recognition in real time by a multitape Turing machine, Resource restricted computability theoretic learning: Illustrative topics and problems, Speed-up theorems in type-2 computations using oracle Turing machines, On splitting recursive sets, On small, reduced, and fast universal accepting networks of splicing processors, The complexity of total order structures, A formalization of multi-tape Turing machines, Almost-everywhere complexity hierarchies for nondeterministic time, The efficient computation of aircraft range problem, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, A note on complexity measures for inductive classes in constructive type theory, On a possible classification of real-time constructed sequences, Time-space tradeoffs for satisfiability, Linear-time simulation of multihead Turing machines, Pushdown cellular automata, Computing in combinatorial optimization, A complexity analysis of bisimilarity for value-passing processes, Complete distributional problems, hard languages, and resource-bounded measure, The complexity of the word problems for commutative semigroups and polynomial ideals, Fast on-line integer multiplication, Succinctness as a source of complexity in logical formalisms, Data structures for distributed counting, Deterministic Turing machines in the range between real-time and linear-time., Sparse sets and collapse of complexity classes, The complexity of two-player games of incomplete information, On average time hierarchies, Unifying known lower bounds via geometric complexity theory, An introduction to tile-based self-assembly and a survey of recent results
Cites Work
