Matrix identities and the pigeonhole principle
Matrix identities and the pigeonhole principle
复制标题
DOI：
10.1007/s00153-003-0205-z
复制
发表时间：
2004-01
影响因子：
0.3
通讯作者：
Michael Soltys;A. Urquhart
中科院分区：
文献类型：
--
作者：
Michael Soltys;A. Urquhart
我们表明，短有界深度弗雷格证明矩阵恒等式，如PQ =I <$QP=I（在两个元素的领域），意味着短有界深度弗雷格证明鸽子原理。由于后一个原理已知需要指数大小的有界深度的弗雷格证明，因此矩阵原理的命题版本也需要指数大小的有界深度的弗雷格证明。
We show that short bounded-depth Frege proofs of matrix identities, such asPQ=I⊃QP=I(over the field of two elements), imply short bounded-depth Frege proofs of the pigeonhole principle. Since the latter principle is known to require exponential-size bounded-depth Frege proofs, it follows that the propositional version of the matrix principle also requires bounded-depth Frege proofs of exponential size.