课题基金 / 基金详情

Topics in proof complexity, circuit complexity, and communication complexity

Topics in proof complexity, circuit complexity, and communication complexity
证明复杂性、电路复杂性和通信复杂性主题
批准号：
349763-2007
负责人：
Pitassi, Toniann
金额：
$2.91万
依托单位：
University of Toronto
依托单位国家：
加拿大
项目类别：
Discovery Grants Program - Accelerator Supplements
财政年份：
2009
资助国家：
加拿大
项目状态：
已结题
起止时间：
2009-01-01 至 2010-12-31
来源：
https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=431083
关键词：
Topicsproofcomplexitycircuitcommunication

项目摘要

项目成果

Pitassi, Toniann的其他基金

相似基金

相关文献

中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
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
海外基金