课题基金 / 基金详情

Topics in proof complexity, circuit complexity, and communication complexity

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
关键词：
Topicsproofcomplexitycircuitcommunication

项目摘要

项目成果

Pitassi, Toniann的其他基金

相似基金

相关文献

中文摘要
翻译
一个旨在最终解决P与NP问题的有前途的方法是证明复杂性。存在与给定证明系统相对应的自然算法族：那些在证明系统中可以被验证为正确的算法。因此，证明复杂性给出了一种对求解SAT的算法进行分类的自然方式，并且给定证明系统的下界意味着相应的SAT算法类的下界。例如，割平面证明的下界意味着SAT和其他NP-Hard问题的一大类线性规划算法的下界。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
New Directions in Complexity Theory
  • 批准号：
    RGPIN-2017-06399
  • 项目类别：
    Discovery Grants Program - Individual
  • 资助金额：
    $8.74万
  • 财政年份：
    2021
  • 负责人：
    Pitassi, Toniann
  • 依托单位：
    University of Toronto
New Directions in Complexity Theory
  • 批准号：
    RGPIN-2017-06399
  • 项目类别：
    Discovery Grants Program - Individual
  • 资助金额：
    $4.37万
  • 财政年份：
    2020
  • 负责人：
    Pitassi, Toniann
  • 依托单位：
    University of Toronto
New Directions in Complexity Theory
  • 批准号：
    DGDND-2017-00092
  • 项目类别：
    DND/NSERC Discovery Grant Supplement
  • 资助金额：
    $2.91万
  • 财政年份：
    2019
  • 负责人：
    Pitassi, Toniann
  • 依托单位：
    University of Toronto
New Directions in Complexity Theory
  • 批准号：
    RGPIN-2017-06399
  • 项目类别：
    Discovery Grants Program - Individual
  • 资助金额：
    $4.37万
  • 财政年份：
    2019
  • 负责人：
    Pitassi, Toniann
  • 依托单位：
    University of Toronto
海外基金