Satisfiability, Branch-Width and Tseitin tautologies
- 作者Michael Alekhnovich; Alexander Razborov
- 卷第20卷
- 期第4期
- 印刷ISSN1016-3328
- 电子ISSN1420-8954
- 文件大小680.04KB
- 发表时间2011-12
- DOI10.1007/s00037-011-0033-1
- 页码649-678
Space Complexity in Propositional CalculusAlekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi · SIAM Journal on Computing · 2002
Satisfiability, Branch-Width and Tseitin tautologiesMichael Alekhnovich; Alexander Razborov · 2011
Mutilated chessboard problem is exponentially hard for resolutionMichael Alekhnovich · 2004
Pseudorandom Generators in Propositional Proof ComplexityAlekhnovich, Michael; Ben-Sasson, Eli; Razborov, Alexander A.; Wigderson, Avi · SIAM Journal on Computing · 2004
Lower Bounds fork-DNF Resolution on Random 3-CNFsMichael Alekhnovich · 2011
Resolution Is Not Automatizable Unless W[P] Is TractableAlekhnovich, Michael; Razborov, Alexander A. · SIAM Journal on Computing · 2008
Toward a Model for Backtracking and Dynamic ProgrammingMichael Alekhnovich; Allan Borodin; Joshua Buresh-Oppenheim; Russell Impagliazzo; Avner Magen; Toniann Pitassi · 2011