Modelling the complexity of parallel and VLSI computations with Boolean circuits

 
see the original item page
in the repository's web site and access all digital files if the item*
share




1995 (EN)

Modelling the complexity of parallel and VLSI computations with Boolean circuits (EN)

Papadopoulos, CV (EN)
Andronikos, TS (EN)

Complexity theory seeks to understand the resource requirements inherent in the solution of problems on computers. It also seeks to understand the relative computational power of different models. The Turing model is difficult to work with, in part because of the impossibility of studying strictly finite structures. Boolean circuits are playing a more important role in our understanding of computation. They are useful as models in situations as far removed as VLSI design and parallel computation. The branching program challenges our intuitions. It has been shown in an indirect fashion that constant-width branching programs can 'count', but not exactly how. Algebraic methods give a handle and allow us for the first time to study complicated combinatorial structures. © 1995. (EN)

journalArticle (EN)

VLSI circuits (EN)
Engineering, Electrical & Electronic (EN)
Computer Science, Theory & Methods (EN)
Sequential complexity (EN)
sequential complexity (EN)
Boolean algebra (EN)
Computational complexity (EN)
lower bounds (EN)
Parallel processing systems (EN)
Lower bounds (EN)
Algorithms (EN)
Turing machines (EN)
Logic circuits (EN)
Computer Science, Hardware & Architecture (EN)
Mathematical models (EN)
Boolean circuits (EN)


Microprocessors and Microsystems (EN)

English

1995 (EN)

1 (EN)
0141-9331 (EN)
10.1016/0141-9331(95)93087-Y (EN)
ISI:A1995QK54200006 (EN)
19 (EN)
50 (EN)
43 (EN)

BUTTERWORTH-HEINEMANN LTD (EN)




*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)