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. 1 Introduction Branching program is one of the most interesting topics in complexity theory. For k 2, a width-k branching program for n-bit inputs is a sequence of instructions f(p i ; f i ; g i )g m i=1 such that for each i; 1 i m, 1 p i n and f i ; g i 2 F k , where F k is the monoid consisting of all mappings of [k] = f1; \Delta \Delta \Delta ; kg to itself. Given an input x 2 \Sigma = f0; 1g of length n, for each i, let h i = f i if the p i -th bit of x is a 1 ..