Class Description

ALOGTIME: Logarithmic time alternating RAM

ALOGTIME is the class of languages decidable in logarithmic time by a random access alternating Turing machine.

Known to be equal to UE*-uniform NC1.

Linked From

NC1: Level 1 of NC

See NC for definition.

[KV94] give a family of functions that is computable in NC1, but not efficiently learnable unless there exists an efficient algorithm for factoring Blum integers.

Was shown to equal 5-PBP [Bar89]. On the other hand, width 5 is necessary unless NC1 = ACC0 [BT88].

As an application of this result, NC1 can be simulated on a quantum computer with three qubits, one initialized to a pure state and the remaining two in the maximally mixed state [ASV00]. Surprisingly, [AMP02] showed that only a single qubit is needed to simulate NC1 - i.e. that NC1 is contained in 2-EQBP. (Complex amplitudes are needed for this result.)

Is contained in L [Bor77].

Contains TC0.

NC1 contains the integer division problem [BCH86], even if an L-uniformity condition is imposed [CDL01].

UE*-uniform NC1 is equal to ALOGTIME [RUZ81].

More about...