Computational Complexity

K Wagner, G. W. (1986). Computational Complexity. Springer.

Type

Book

Intellectual base

Review or monograph

Year

1986

Link

no authoritative link yet

Cited by

1 citation across 1 artifact.

Domain-specific

• Linear speedup theorem
  • … distinction between constitutive identity and a convenient observable transfers from A two-tape machine is re-encoded so several old symbols and transitions are handled per simulator step. to A complexity proof ignores a fixed multiplicative time constant only after checking the theorem's machine-model assumptions..

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:65c0ce850a4a · see in the full table