The Library
On the construction of parallel computers from various bases of Boolean functions
Tools
Tools
Tools
Parberry, Ian and Goldschlager, L. (1983) On the construction of parallel computers from various bases of Boolean functions. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-048.pdf - Other - Requires a PDF viewer. Download (1094Kb) | Preview |
Abstract
The effects of bases of two-input boolean functions are characterised 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 difficult, and renders extended Turing machines and conglomerates equal to general parallel computers. A class of problems called EP arises naturally 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 to a problem (NP). Tournament isomorphism is a member of EP.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Parallel computers, Algebra, Boolean | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | 1983 | ||||
| Dates: |
|
||||
| Number: | Number 48 | ||||
| Number of Pages: | 16 | ||||
| DOI: | CS-RR-048 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | I. Parberry and L.M. Goldschlager, On the Construction of Parallel Computers from Various Bases of Boolean Functions, Theoretical Computer Science 43 (1), pp. 43-58 (1986) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
