A note on monotone complexity and the rank of matrices |
| |
Authors: | Anna Gál Pavel Pudlák |
| |
Affiliation: | a Department of Computer Science, University of Texas at Austin, Austin, TX 78712, USA b Mathematical Institute, Academy of Sciences of the Czech Republic, Prague, Czech Republic |
| |
Abstract: | We shall give simpler proofs of some lower bounds on monotone computations. We describe a simple condition on combinatorial structures, such that the rank of the matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be constructed from self-avoiding families. As a corollary, we obtain an upper bound on the size of self-avoiding families, which solves a problem posed by Babai and Gál Combinatorica 19 (3) (1999) 301-319]. |
| |
Keywords: | Computational complexity Lower bounds Span programs |
本文献已被 ScienceDirect 等数据库收录! |
|