Topics in proof complexity, circuit complexity, and communication complexity

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

• 批准号: 228106-2007
• 负责人: Pitassi, Toniann
• 金额: $ 3.64万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2009
• 资助国家: 加拿大
• 起止时间: 2009-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=425349
• 关键词: 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难问题的广泛的线性规划算法的下界。