Modelling the complexity of parallel and VLSI computations with Boolean circuits

δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο

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

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

N/A (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)


VLSI circuits (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)
Mathematical models (EN)
Boolean circuits (EN)

Εθνικό Μετσόβιο Πολυτεχνείο (EL)
National Technical University of Athens (EN)

Microprocessors and Microsystems (EN)



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.