Tradeoffs for language recognition on alternating machines

AbstractThe alternating machine having a separate input tape with k two-way, read-only heads, and a certain number of internal configurations, AM(k), is considered as a parallel computing model. For the complexity measure TIME · SPACE · PARALLELISM (TSP), the optimal lower bounds Ω(n2) and Ω(n3/2) respectively are proved for the recognition of specific languages on AM(1) and AM(k) respectively. For the complexity measure REVERSALS · SPACE · PARALLELISM (RSP), the lower bound Ω(n1/2) is established for the recognition of a specific language on AM(k). This result implies a polynomial lower bound on PARALLEL TIME · HARDWARE of parallel RAM's.Lower bounds on the complexity measures TIME · SPACE and REVERSALS · SPACE of nondeterministic machines are direct consequences of the result introduced above.All lower bounds obtained are substantially improved in the case that SPACE⩾ nɛ for 0<ɛ