首页 | 官方网站   微博 | 高级检索  
     


On the complexity of regular resolution and the Davis-Putnam procedure
Authors:Zvi Galil
Affiliation:Computer Sciences Department, IBM Thomas J. Watson Research Centre, Yorktown Heights, NY 10598, U.S.A.
Abstract:For infinitely many n > 0 we construct contradictory formulas αn in conjunctive form with n literals such that every regular proof tree which proves the contradiction must contain 2cn distinct clauses for some c > 0. This implies a 2cn lower bound for the number of distinct clauses which are generated by the Davis-Putnam procedure applied to αn using any order of variable elimination.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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

京公网安备 11010802026262号