Note on Problems which are Hard for some Weakly Connected Parallel Architectures

Abstract

In this paper the lower bound technique, based on information content, for special models of VLSI circuits defined by some topological restrictions is investigated. The assertion bounding possibilities of speeding up a VLSI  computation by increasing the number of processors for circuits with f/separators is presented. Further possibilities of applying these results to obtain stronger lower bounds or proofs of noneffectivity of speeding up computation for some classes of problems and separators are shown.