On the construction of parallel computers from various basis of Boolean functions (Q1083204)

At first the space complexity of the circuit value problem (CVP) over two-input bases is studied. It is found out that, for the two-input bases B, either \(CVP_ B\) is log space complete for P, or it can be computed in \(O(\log^ 2n)\) space. After that, the extended Turing machine (ETM) is introduced and it is proved that the ETM over two-input Boolean bases B are as powerful as parallel machines iff the CVP over basis B is log space complete for P. The case of ETM with domain \(D=\{0,1\}\) and basis \(B\subseteq B_ 2\) is studied in more detail. Networks over basis B are considered. To eliminate NOT gates, the idea of ''double rail logic'' is used. A particular basis \(B\subseteq B_ 2\) can be used to build general purpose machines iff B is P-complete. The conditions for that are proved. It appears that \(\{\wedge,\vee \}\) is not a powerful computational basis for planar circuits.