Proof complexity of matrix algebra

证明矩阵代数的复杂性

• 批准号: 249895-2011
• 负责人: SoltysKulinicz, Michael
• 金额: $ 1.75万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=547441
• 关键词: Proof; complexity; matrix; algebra

Proof Complexity (PC) is an area of theoretical computer science that deals with the computational complexity of formal reasoning. PC is intimately connected to major open problems in complexity theory (notably the famous "P vs NP" problem, which lately received a high-degree of notoriety in the press; see, for example, the Globe and Mail article by Kate Allen from August 20, 2010), and to the field of automated theorem proving.

证明复杂性（Proof Complexity，PC）是理论计算机科学的一个领域，涉及形式推理的计算复杂性。 PC与复杂性理论中的主要开放问题（特别是著名的“P vs NP”问题，最近在媒体上引起了很大的关注;例如，参见Kate艾伦于2010年8月20日在地球仪和邮报上发表的文章）以及自动定理证明领域密切相关。