[PDF][PDF] A hierarchy for nondeterministic time complexity
SA Cook - Proceedings of the fourth annual ACM symposium on …, 1972 - dl.acm.org
The purpose of this paper is to prove the following result: Theorem 1 For any real numbers
r1, r2, 1≤ r1< r2, there is a set A of strings which has nondeterministic time complexity nr2 …
r1, r2, 1≤ r1< r2, there is a set A of strings which has nondeterministic time complexity nr2 …
[PDF][PDF] Separating nondeterministic time complexity classes
JI Seiferas, MJ Fischer, AR Meyer - Journal of the ACM (JACM), 1978 - dl.acm.org
Techniques such as those of Meyer and Stockmeyer [21], Meyer [19], Stockmeyer and Meyer
[29], Hunt [14], MJ Fischer and Rabin [8], and Stockmeyer [28] sometimes show that a …
[29], Hunt [14], MJ Fischer and Rabin [8], and Stockmeyer [28] sometimes show that a …
On determinism versus non-determinism and related problems
WJ Paul, N Pippenger, E Szemeredi… - … Annual Symposium on …, 1983 - ieeexplore.ieee.org
On determinism versus non-determinism and related problems Page 1 ON DETERMINISM
VERSUS NON-DETERMINISM AND RELATED PROBLEMS (Preliminary Version) Wolfgang J …
VERSUS NON-DETERMINISM AND RELATED PROBLEMS (Preliminary Version) Wolfgang J …
[图书][B] On some central problems in computational complexity.
J Simon - 1975 - search.proquest.com
2.2 Machine models Throughout this thesis we will be considering computing devices as
acceptors of sets of sequences, or languages. Al ternatively we may view these as 0-1 …
acceptors of sets of sequences, or languages. Al ternatively we may view these as 0-1 …
[PDF][PDF] Computations with a restricted number of nondeterministic steps
CMR Kintala, PC Fischer - Proceedings of the ninth annual ACM …, 1977 - dl.acm.org
Nondeterminism is one of the most elusive concepts in computing. In this paper we direct
our efforts towards viewing nondeterminism as an additional resource at the disposal of time …
our efforts towards viewing nondeterminism as an additional resource at the disposal of time …
Relationships between nondeterministic and deterministic tape complexities
WJ Savitch - Journal of computer and system sciences, 1970 - Elsevier
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine
on a deterministic Turing machine is investigated. Results include the following: Theorem. A …
on a deterministic Turing machine is investigated. Results include the following: Theorem. A …
A Turing machine time hierarchy
S Žák - Theoretical Computer Science, 1983 - Elsevier
The time separation results concerning classes of languages over a single-letter alphabet
accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer …
accepted by multi-tape nondeterministic Turing machines, well-known from Seiferas, Fischer …
[PDF][PDF] On the time and tape complexity of languages I
HB Hunt III - Proceedings of the fifth annual ACM symposium on …, 1973 - dl.acm.org
We investigate the following:(1) the relationship between the classes of languages accepted
by deterministic and nondeterministic polynomial time bounded Turing machines;(2) the …
by deterministic and nondeterministic polynomial time bounded Turing machines;(2) the …
The complexity of finite functions
RB Boppana, M Sipser - Algorithms and complexity, 1990 - Elsevier
Publisher Summary This chapter discusses the complexity of finite functions. A deterministic
Turing machine consists of a finite control and a finite collection of tapes each with a head …
Turing machine consists of a finite control and a finite collection of tapes each with a head …
Some results on tape-bounded Turing machines
JE Hopcroft, JD Ullman - Journal of the ACM (JACM), 1969 - dl.acm.org
Classes of tape-bounded Turing machines similar to the on-line and off-line Turing
machines, but without the restrictions that each machine halt and be deterministic, are …
machines, but without the restrictions that each machine halt and be deterministic, are …