• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>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，从Barrington的定理中几乎立即计算矩阵的决定因素的硬度。 Barrington展示了如何在任何不可溶解的组上表达NC ^ 1作为产品计划。我们直接从Barrington的产品计划构建一个简单的矩阵，其决定因素计算产品计划的解决方案数量。这给出了一个简单的证据证明，根据代数的特性，计算含有不可溶解组的代数上的代数的决定因素。为了表明，计算定制符合非容态矩阵代数，其单位组是可解决的，我们构建了新的产品计划（本着Barrington的精神），即使代数的单位组是可解决的，也可以评估3SAT公式。非传染性决定因素的硬度已经知道，最近通过重组勇敢的（相当复杂）减少＃3SAT来计算永久性。我们的重点是获得概念上更简单的证明。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号