Class Description

SFk: Width-k Bottleneck Turing Machines

The class of decision problems solvable by a k-bottleneck Turing machine. This is a machine that, after a polynomial amount of time, erases everything on the tape except for a single k-valued "safe-storage". There's also a counter recording the number of erasings, which is in effect a non-deterministic witness. For example, SF2 contains both ⊕P and NP by using the counter as a witness.

Defined in [CF91], where it was also shown that SF5 = PSPACE.

The complexity of SF2, SF3, and SF4 was studied in [Ogi94] and [Her97]. The following result of those authors is among the caged beasts of the Complexity Zoo:

SF4 is contained in BP ⊕PMod_3P ^ ⊕P ^ Mod_3P ^ ⊕P

(Here the BP operator means that one makes the class into a bounded-error probabilistic class, the same way one makes P into BPP and NP into AM.)

Linked From

No class.