Nonerasing, counting, and majority over the linear time hierarchy
In this paper, we investigate several extensions of the linear time hierarchy (denoted by LTH). We first prove that it is not necessary to erase the oracle tape between two successive oracle calls, thereby lifting a common restriction on LTH machines. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that the computational power of the majority operator is equivalent to that of the exact counting operator in both contexts. (C) 2002 Elsevier Science (USA).
computational and structural complexity logic in computer science rudimentary relations counting classes