Translational Lemmas for Alternating TMs and PRAMs

摘要

We present translational lemmas for alternating Turing machines (ATMs) and parallel random access machines (PRAMs), and apply them to obtain tight hierarchy results on ATM- and PRAM-based complexity classes. It is shown that, for any small rational constant ε, there is a language which can be accepted by a c(9 + ε) log~r n-time d(4 + ε) log n-space ATM with l worktapes but not by any c log~r n-time d log n-space ATM with the same l worktapes if the number of tape symbols is fixed. Here, c, d > 0 and r > 1 are arbitrary rational constants, and l ≥ 2 is an arbitrary integer. It is also shown that, for any small rational constant ε, there is a language which can be accepted by a c(1 + ε) log~(r_1) n-time PRAM with n~(r_2) processors but not by any clog~(r_1) n-time PRAM with n~(r_2(1+ε)) processors, where c > 0, r_1 > 1, and r_2 ≥ 1 are arbitrary rational constants.