讨论组:复杂性、密码学与算法组
标题:Short Propositional Refutations for Dense Random 3CNF Formulas
演讲人: Iddo Tzameret
时间: 2011-04-08 14:00-2011-04-08 15:30
地点:FIT 1-222

内容:

This is a talk about propositional proofs and satisfiability. First, I am going to give a short high level introduction to proof complexity. Then, I will show that almost all 3CNF formulas with high enough clause-to-variable ratio have short propositional refutations, already in a fairly weak propositional proof system.

*No prior knowledge in proof complexity is assumed.*



人物介绍: