The proof complexity of matrix algebra

矩阵代数的证明复杂度

• 批准号: 249895-2006
• 负责人: SoltysKulinicz, Michael
• 金额: $ 1.38万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363987
• 关键词: 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), and to the field of automated theorem proving.   My research is particularly concerned with the application of fast parallel algorithms for matrix computations to upper and lower bounds in propositional proof systems.

证明复杂性（Proof Complexity，PC）是理论计算机科学的一个领域，主要研究形式推理的计算复杂性，PC与复杂性理论中的主要开放问题（特别是著名的“P vs NP”问题）以及自动定理证明领域密切相关。 我的研究是特别关注的应用程序的快速并行算法的矩阵计算的上限和下限的命题证明系统。