Lecture 2

David Mix Barrington, A. M. (2000). Lecture 2: The Complexity of Some Problems.

Type

Unclassified

Intellectual base

Unclassified

Year

2000

Link

no authoritative link yet

Cited by

1 citation across 1 artifact.

Domain-specific

• AC0
  • AC0 is the first alternating-circuit level, is closed under standard Boolean composition and cannot compute parity under the usual uniform or nonuniform definitions, though uniformity conventions matter.

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:34589633504d · see in the full table