Is it easier to solve two communication problems together than separately? This question is related to the complexity of the composition of boolean functions. Based on this relationship, an approach to separating NC 1 from P is outlined. Furthermore, it is shown that the approach provides a new proof of the separation of monotone NC 1 from monotone P.
|Original language||English (US)|
|Number of pages||14|
|State||Published - Sep 1 1995|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computational Theory and Mathematics
- Computational Mathematics