On the construction of parallel computers from various bases of boolean functions

AbstractThe effects of bases of two-input Boolean functions are characterized in terms of their impact on some questions in parallel computation. It is found that a certain set of bases (called the P-complete set), which are not necessarily complete in the classical sense, apparently makes the circuit value problem from difficult, and renders extended. Turing machines and networks of Boolean gates equal to general parallel computers. A class of problems called EP naturally arises from this study, relating to the parity of the number of solutions to a problem, in contrast to previously defined classes concerning the count of the number of solutions (#P) or the existence of solutions (NP). Tournament isomorphism is a member of EP