๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Bounds for the Element Distinctness Problem on one-tape Turing machines

โœ Scribed by Holger Petersen

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
62 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

The reduction of tape reversals for off-
The reduction of tape reversals for off-line one-tape Turing machines
โœ Patrick C. Fischer ๐Ÿ“‚ Article ๐Ÿ“… 1968 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 554 KB

For off-line one-tape Turing machines the number of tape reversals required for various computations may be uniformly reduced by an arbitrary constant factor. ## Introduction In the studies of specific measures of computational complexity it has always been of interest to determine the "speed-up"