Relationships between Nondeterministic and Deterministic Tape Complexities

Savitch, W. J. (1970). Relationships between Nondeterministic and Deterministic Tape Complexities. Journal of Computer and System Sciences, 4(2), 177-192.

Type

Journal article

Intellectual base

Primary research

Year

1970

DOI

10.1016/s0022-0000(70)80006-x

Link

https://doi.org/10.1016/s0022-0000(70)80006-x

Cited by

1 citation across 1 artifact.

Domain-specific

• EXPSPACE
  • The entry uses classical deterministic decision complexity under standard machine robustness assumptions; quantum, randomized, parameterized, descriptive, and streaming space classes require separate definitions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:15b2cc7784f0 · see in the full table