Relations Among Complexity Measures

DOI10.1145/322123.322138zbMath0405.68041OpenAlexW2045717693MaRDI QIDQ4191603

Michael J. Fischer, Nicholas J. Pippenger

Publication date: 1979

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322123.322138

zbMATH Keywords

MeasureLower BoundsComputational ComplexityTime ComplexityTuring MachineOn-Line SimulationCombinational Logic NetworkCost of NetworksOblivious MachineStorage TapesTree- Structured Storage Media

Mathematics Subject Classification ID

Related Items (76)

Local Reductions ⋮ Speedup of determinism by alternation for multidimensional Turing machines ⋮ A simple construction of iO for Turing machines ⋮ What is a sorting function? ⋮ Short propositional formulas represent nondeterministic computations ⋮ On the simulation of many storage heads by one ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Secure Multiparty RAM Computation in Constant Rounds ⋮ Constant-Round Maliciously Secure Two-Party Computation in the RAM Model ⋮ Local reduction ⋮ Delegating RAM Computations ⋮ Optimal dynamic embedding of X-trees into arrays ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ Adaptively secure computation for RAM programs ⋮ Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings ⋮ The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ A new complete language for DSPACE(log n) ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Checking the correctness of memories ⋮ A survey on temporal logics for specifying and verifying real-time systems ⋮ Laconic function evaluation for Turing machines ⋮ Data encodings and their costs ⋮ On alternation ⋮ On the simulation of quantum Turing machines. ⋮ Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms. ⋮ Tight hierarchy of data-independent multi-head automata ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ 3-party distributed ORAM from oblivious set membership ⋮ On guarded extensions of MMSNP ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ The pseudorandom oracle model and ideal obfuscation ⋮ The size and depth of layered Boolean circuits ⋮ On uniform circuit complexity ⋮ On time versus space. II ⋮ Classifying the computational complexity of problems ⋮ An information-theoretic approach to time bounds for on-line computation ⋮ On the complexity of 2-output Boolean networks ⋮ Parallel models of computation: An introductory survey ⋮ Simulations among multidimensional Turing machines ⋮ A fast implementation of a multidimensional storage into a tree storage ⋮ The complexity of deciding reachability properties of distributed negotiation schemes ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ The complexity of contract negotiation ⋮ Perennial secure multi-party computation of universal Turing machine ⋮ Generic oracles, uniform machines, and codes ⋮ Shorter arithmetization of nondeterministic computations ⋮ On quasilinear-time complexity theory ⋮ Revisiting the simulation of quantum Turing machines by quantum circuits ⋮ On the power of several queues ⋮ Linear speed-up does not hold on Turing machines with tree storages ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Extensions to Barrington's M-program model ⋮ Constant-round maliciously secure two-party computation in the RAM model ⋮ The complexity of monotone boolean functions ⋮ Determination of equivalence between quantum sequential machines ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Oblivious Parallel RAM and Applications ⋮ ON THE POWER OF FAMILIES OF RECOGNIZER SPIKING NEURAL P SYSTEMS ⋮ Information and computation: Classical and quantum aspects ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ Improved simulation of nondeterministic Turing machines ⋮ Time-space tradeoffs for satisfiability ⋮ On some FPT problems without polynomial Turing compressions ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Characterization of all optimal networks for a simultaneous computation of AND and NOR ⋮ Complexity lower bounds for machine computing models ⋮ Unnamed Item ⋮ Unnamed Item ⋮ PAC-learning gains of Turing machines over circuits and neural networks ⋮ Uncontrollable computational growth in theoretical physics ⋮ Multi-head finite automata: Data-independent versus data-dependent computations ⋮ On the computational complexity of qualitative coalitional games ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines ⋮ Combinatorial PCPs with short proofs

This page was built for publication: Relations Among Complexity Measures