Topics in proof complexity, circuit complexity, and communication complexity

证明复杂性、电路复杂性和通信复杂性主题

• 批准号: 228106-2007
• 负责人: Pitassi, Toniann
• 金额: $ 3.64万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2011
• 资助国家: 加拿大
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=478691
• 关键词: Topics; proof; complexity; circuit; communication

A promising approach aimed at ultimately resolving the P versus NP question is proof complexity. There is a natural family of algorithms corresponding to a given proof system: those algorithms that can be verified to be correct in the proof system. Thus proof complexity gives a natural way of classifying algorithms for solving SAT, and lower bounds for a given proof system implies lower bounds for the corresponding class of algorithms for SAT. For example, lower bounds for Cutting Planes proofs implies lower bounds for a broad class of linear-programming algorithms for SAT and other NP-hard problems.

一种旨在最终解决P与NP问题的有前途的方法是证明复杂性。与给定的证明系统相对应的天然算法家族：可以验证在证明系统中正确的算法。因此，证明复杂性提供了一种自然的方法来分类用于求解SAT的算法，并且给定证明系统的下限意味着SAT的相应算法类别的下限。例如，切割平面证明的下限意味着针对SAT和其他NP硬性问题的广泛线性编程算法的下限。