Speedups of deterministic machines by synchronous parallel machines (Q1074339)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Speedups of deterministic machines by synchronous parallel machines |
scientific article; zbMATH DE number 3947630
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Speedups of deterministic machines by synchronous parallel machines |
scientific article; zbMATH DE number 3947630 |
Statements
Speedups of deterministic machines by synchronous parallel machines (English)
0 references
1985
0 references
The paper presents new speedups of deterministic multitape Turing machines by both fixed and variable structure parallel machines. Namely, it is shown that DTIME(T)\(\subseteq ATIME(T/\log T)\) and DTIME(T)\(\subseteq PRAM\)-time(\(\sqrt{T})\). These improve many previously known results.
0 references
multitape Turing machines
0 references
0 references
0.8764429
0 references
0.8695287
0 references
0.8643902
0 references
0.8556138
0 references
0.8553299
0 references
0.8547244
0 references
