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


Mutilated chessboard problem is exponentially hard for resolution
Authors:Michael Alekhnovich  
Affiliation:

Laboratory for Computer Science, MIT, 545 Technology Square, Cambridge MA 02139, USA

Abstract:Mutilated chessboard principle CBn says that it is impossible to cover by domino tiles the chessboard 2n×2n with two diagonally opposite corners removed. We prove Image lower bound on the size of minimal resolution refutation of CBn.
Keywords:Propositional proof complexity  Resolution  Lower bounds
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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