首页 | 本学科首页   官方微博 | 高级检索  
     


An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
Authors:Jan Krají     ek,Pavel Pudl  k,Alan Woods
Affiliation:Jan Krajíček,Pavel Pudlák,Alan Woods
Abstract:We prove lower bounds of the form exp(nε d), εd > 0, on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth d, for any constant d. This is the largest lower bound for the strongest proof system, for which any superpolynomial lower bounds are known.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号