On nondeterminism in parallel computation (Q1099612)

Nondeterministic parallel complexity classes are investigated using two different non-deterministic versions of the hardware modification machine model. Differences in the effects of adding nondeterminism to parallel machines can be traced to the amount of the nondeterminism available at each time step. Nondeterministic complexity classes defined by simultaneous bounds on both hardware and parallel time are also examined.