On Relating Time and Space to Size and Depth

DOI10.1137/0206054zbMath0366.68039OpenAlexW2088141885WikidataQ29395034 ScholiaQ29395034MaRDI QIDQ4142697

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206054

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items

Oracle computations in parallel numerical linear algebra, Bits and relative order from residues, space efficiently, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Parallel pointer machines, Space-efficient recognition of sparse self-reducible languages, Accurate approximate diagnosis of (controllable) stochastic systems, The complexity of elementary algebra and geometry, On nondeterminism in parallel computation, Some results on uniform arithmetic circuit complexity, An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, A generalization of Spira's theorem and circuits with small segregators or separators, Parallel algorithms for solvable permutation groups, Parallel evaluation of arithmetic circuits, The complexity of intersecting finite automata having few final states, Amplifying circuit lower bounds against polynomial time, with applications, Parallel approximation of min-max problems, A measure of relativized space which is faithful with respect to depth, Complexity theory of parallel time and hardware, Parallélisation d'algorithmes avec un nombre fixe de processeurs, Skew circuits of small width, Descriptive complexity of deterministic polylogarithmic time and space, A new complete language for DSPACE(log n), Some complexity theoretic aspects of AC rewriting, On Goles' universal machines: a computational point of view, RelativizedNC, Nondeterministic seedless oritatami systems and hardness of testing their equivalence, Markov chains and unambiguous automata, Tree-size bounded alternation, Bounded size dictionary compression: SC$^{k}$-completeness and NC algorithms., Adaptive logspace reducibility and parallel time, The size and depth of layered Boolean circuits, Parallelizing time with polynomial circuits, On the complexity of regular-grammars with integer attributes, Small space analogues of Valiant's classes and the limitations of skew formulas, On uniform circuit complexity, Classifying the computational complexity of problems, Parallelism and fast solution of linear systems, Parallel models of computation: An introductory survey, Number of quantifiers is better than number of tape cells, Efficient parallel algorithms for linear recurrence computation, Space-bounded quantum complexity, Extensional Uniformity for Boolean Circuits, Properties that characterize LOGCFL, On some derivation mechanisms and the complexity of their Szilard languages, The complexity of computing the number of strings of given length in context-free languages, Oracle branching programs and Logspace versus $P^*$, Highly parallel computations modulo a number having only small prime factors, Epsilon-net method for optimizations over separable states, Reversible simulation of space-bounded computations, A note on parallel and alternating time, Parallel algebraic reductions among numerical problems, The complexity of circuit value and network stability, Bounded arithmetic for NC, ALogTIME, L and NL, Closed timelike curves make quantum and classical computing equivalent, Advice Coins for Classical and Quantum Computation, Multiplication, division, and shift instructions in parallel random access machines, Space Hardness of Solving Structured Linear Systems., On iterated integer product, Tight complexity bounds for term matching problems, Unambiguity of circuits, Division in logspace-uniformNC¹, Unnamed Item, On the complexity of some problems on groups input as multiplication tables, A $\Sigma_2^P \cup \Pi_2^P$ Lower Bound Using Mobile Membranes, Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes, On the parallel complexity of the polynomial ideal membership problem, The Orthogonal Vectors Conjecture for Branching Programs and Formulas, Nondeterministic $NC^1$ computation, On the complexity of counting components of algebraic varieties, Positive versions of polynomial time, Nondeterministic Seedless Oritatami Systems and Hardness of Testing Their Equivalence, Nonuniform complexity classes specified by lower and upper bounds, Optical computing, An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, Bandwidth constraints on problems complete for polynomial time, Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval, A note on the parallel computation thesis, Computing a context-free grammar-generating series, Multiplication is the easiest nontrivial arithmetic function, Quantum neural networks, Parallel solutions to geometric problems in the scan model of computation, Nondeterministics circuits, space complexity and quasigroups, Uncontrollable computational growth in theoretical physics, Speedups of deterministic machines by synchronous parallel machines, Logics which capture complexity classes over the reals