• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Conference on Computational Complexity >Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington#039;s Theorem
【24h】

Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington#039;s Theorem

机译：非可交换行列式很难：使用Barrington定理的扩展的简单证明

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington's Theorem. Barrington showed how to express a NC^1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington's product program whose determinant counts the number of solutions to the product program. This gives a simple proof that computing the determinant over algebras containing a non-solvable group is #P-hard or Mod_pP-hard, depending on the characteristic of the algebra. To show that computing the determinant is hard over noncommutative matrix algebras whose group of units is solvable, we construct new product programs (in the spirit of Barrington) that can evaluate 3SAT formulas even though the algebra's group of units is solvable. The hardness of noncommutative determinant is already known, it was recently proven by retooling Valiant's (rather complex) reduction of #3SAT to computing the permanent. Our emphasis here is on obtaining a conceptually simpler proof.
机译：我们表明，对于许多非交换代数A，计算矩阵在A上的行列式的难度几乎是从巴林顿定理得出的。 Barrington展示了如何将NC ^ 1电路表示为任何不可解组的乘积程序。我们直接从Barrington的产品程序构造一个简单的矩阵，该矩阵的行列式计算该产品程序的解决方案数量。这提供了一个简单的证据，取决于代数的特性，计算包含不可解基团的代数的行列式是＃P-hard或Mod_pP-hard。为了证明行列式对单位组可解的非交换矩阵代数比较困难，我们构建了新产品程序（本着Barrington的精神），即使该代数的单位组可解，它也可以评估3SAT公式。非可交换行列式的硬度是已知的，最近通过重新构造Valiant（相当复杂）的＃3SAT简化来计算永久变量来证明这一点。我们在这里的重点是获得概念上更简单的证明。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号