On the power of synchronization. (English) Zbl 0689.68074

Summary: A new model of parallel computations, the so-called Synchronized Turing Machines are presented. They are a generalization of standard alternating Turing machines. In addition to alternation these machines make use of a new computational resource-synchronization. Thanks to synchronization the parallel processes of this machine can make the same nondeterministic decisions, if necessary, and, hence, communicate with each other in a restricted way. It will be shown that corresponding computational time, and space complexity classes are related to standard ones in a natural way. Consequently nondeterministic polynomial space or synchronized polynomial time will be shown to be strictly contained in synchronized polynomial space. Thus synchronized Turing Machines present the first known fundamental machine model which can be proved to be more efficient than deterministic or nondeterministic Turing machines, or for which space is a substantially more efficient computational resource than time.


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)