Simulating time with square-root space
From MaRDI portal
Cites work
- A probabilistic remark on algebraic program testing
- A space bound for one-tape multidimensional Turing machines
- A space lower bound for \(st\)-connectivity on node-named JAGs
- Algorithms and Computation
- Amplifying circuit lower bounds against polynomial time, with applications
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Boolean function complexity. Advances and frontiers.
- Catalytic approaches to the tree evaluation problem
- Circuit size is nonlinear in depth
- Classes of languages and linear-bounded automata
- Computational Complexity
- Computational Complexity
- Easiness amplification and uniform circuit lower bounds
- Expanders, randomness, or time versus space
- Explicit OR-dispersers with polylogarithmic degree
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- Hardness vs randomness
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 1142308 (Why is no real title available?)
- scientific article; zbMATH DE number 3992933 (Why is no real title available?)
- scientific article; zbMATH DE number 3363526 (Why is no real title available?)
- Improved simulation of nondeterministic Turing machines
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- On the complexity of k-SAT
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
- On Time Versus Space
- On time versus space III
- On time versus space. II
- Optimal Dynamic Embedding of Trees into Arrays
- Pebbles and branching programs for tree evaluation
- Random access to advice strings and collapsing results
- Relations Among Complexity Measures
- Relations Between Time and Tape Complexities
- Some Time-Space Tradeoff Results Concerning Single-Tape and Offline TM’<scp>s</scp>
- Space-bounded simulation of multitape turing machines
- Speedups of deterministic machines by synchronous parallel machines
- Tape bounds for time-bounded Turing machines
- The complexity of satisfiability of small depth circuits
- The problem of space invariance for sequential machines
- Tight Lower Bounds for st-Connectivity on the NNJAG Model
- Time-space lower bounds for satisfiability
- Trading time and space in catalytic branching programs
- Two-Tape Simulation of Multitape Turing Machines
- Undirected connectivity in log-space
This page was built for publication: Simulating time with square-root space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7305345)
