Pages that link to "Item:Q5526975"
From MaRDI portal
The following pages link to Two-Tape Simulation of Multitape Turing Machines (Q5526975):
Displaying 50 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- On quasilinear-time complexity theory (Q672330) (← links)
- On the power of several queues (Q685436) (← links)
- A formalization of multi-tape Turing machines (Q744986) (← links)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes (Q756423) (← links)
- Improved simulation of nondeterministic Turing machines (Q764330) (← links)
- Data structures for distributed counting (Q794431) (← links)
- Minimizing access pointers into trees and arrays (Q795505) (← links)
- Time hierarchies for cryptographic function inversion with advice (Q843601) (← links)
- Milking the Aanderaa argument (Q918198) (← links)
- Complexity lower bounds for machine computing models (Q1057651) (← links)
- Tape versus queue and stacks: The lower bounds (Q1109567) (← links)
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time (Q1113670) (← links)
- On time hierarchies (Q1137384) (← links)
- Hierarchy of complexity of computation of partial functions with values 0 and 1 (Q1149431) (← links)
- An improved simulation result for ink-bounded Turing machines (Q1151038) (← links)
- Complexity of algorithms and computations (Q1153141) (← links)
- An information-theoretic approach to time bounds for on-line computation (Q1156484) (← links)
- The network complexity and the Turing machine complexity of finite functions (Q1230622) (← links)
- Relations between diagonalization, proof systems, and complexity gaps (Q1254105) (← links)
- Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465) (← links)
- On average time hierarchies (Q1313704) (← links)
- On the simulation of many storage heads by one (Q1348528) (← links)
- Deterministic multitape automata computations (Q1393939) (← links)
- A hierarchy for nondeterministic time complexity (Q1394124) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- Local reduction (Q1641001) (← links)
- Domino-tiling games (Q1822501) (← links)
- Linear-time simulation of multihead Turing machines (Q1825664) (← links)
- Time bounded random access machines (Q1844708) (← links)
- A linear time two tape merge (Q1845474) (← links)
- PAC-learning gains of Turing machines over circuits and neural networks (Q2111729) (← links)
- Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts (Q2136854) (← links)
- Modeling multitape Minsky and Turing machines by three-tape Minsky machines (Q2226960) (← links)
- Generality's price: Inescapable deficiencies in machine-learned programs (Q2368918) (← links)
- Time-restricted sequence generation (Q2537897) (← links)
- k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines) (Q2547545) (← links)
- Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines) (Q2547546) (← links)
- On non-determinacy in simple computing devices (Q2550291) (← links)
- Writing stack acceptors (Q2554233) (← links)
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata (Q2558752) (← links)
- On two-way multihead automata (Q2559145) (← links)
- Relativized depth (Q2686103) (← links)
- Turing Machines for Dummies (Q2891358) (← links)
- Local Reductions (Q3448833) (← links)
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines (Q3748273) (← links)
- On the complexity of finite, pushdown, and stack automata (Q4121398) (← links)
- Towards the Actual Relationship Between NP and Exponential Time (Q4238424) (← links)
