On Serializable Languages

Cai and Furst introduced the notion of bottleneck Turing machines and showed that the languages recognized by width-5 bottleneck Turing machines are exactly those in PSPACE. Computational power of bottleneck Turing machines with width fewer than 5 is investigated. It is shown that width-2 bottleneck Turing machines capture polynomial-time many-one closure of nearly near-testable sets. For languages recognized by bottleneck Turing machines with intermediate width 3 and 4, some lower and upper bounds are shown