RELATIONS AMONG SIMULTANEOUS COMPLEXITY CLASSES OF NONDETERMINISTIC AND ALTERNATING TURING-MACHINES

Ruzzo [Tree-size bounded alternation, J. Comput. Syst. Sci. 21] introd uced the notion of tree-size for alternating Turing machines (ATMs) an d showed that it is a reasonable measure for classification of complex ity classes. We establish in this paper that computations by tree-size and space simultaneously bounded ATMs roughly correspond to computati ons by time and space simultaneously bounded nondeterministic TMs (NTM s). We also show that not every polynormal time bounded and sublinear space simultaneously bounded NTM can be simulated by any deterministic TM with a slightly increased time bound and a slightly decreased spac e bound simultaneously.