首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Variants of the Determinant polynomial and VP-completeness
  • 本地全文:下载
  • 作者:Prasad Chaugule ; Nutan Limaye ; Shourya Pandey
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2020
  • 卷号:2020
  • 页码:1-26
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:The determinant is a canonical VBP-complete polynomial in the algebraic complexity setting. In this work, we introduce two variants of the determinant polynomial which we call StackDetnpXq and CountDetnpXq and show that they are VP and VNP complete respectively under p-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely clow sequences, by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).
国家哲学社会科学文献中心版权所有