文章基本信息

标题：Monotone complexity and the rank of matrices
本地全文：下载
作者：Pavel Pudlak
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The rank of a matrix has been used a number of times to prove lower bounds on various types of complexity. In particular it has been used for the size of monotone formulas and monotone span programs. In most cases that this approach was used, there is not a single matrix associated with the function in question, but one has to minimize the rank over a set of matrices (eg., \cite{razborov,gal}). Usually, this makes the techniques very difficult to apply. In this note we define a certain combinatorial structure that enables us to use the rank lower bound directly. We shall not prove new lower bound, we only show that some previous lower bounds on monotone span programs can be simply derived using this structure. It is open whether our approach can produce better lower bounds.
关键词：monotone complexity , rank of a matrix , Span Programs