In the paper The complexity of tensor calculus by C. Damm, M. Holzer and P. McKenzie (link), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor formulae over $ \mathbb{N} $, i.e., the semiring of natural numbers including zero. With that, the authors reached the conclusion that "For any infinite field $ \mathbb{F} $, $ \operatorname{val}_{\mathbb{F}} $ is #P-hard under polytime Turing reductions." by claiming that "$ \mathbb{N} $ is embedded in every infinite field." (See Corollary 10 in the original paper)

My question is exactly about the last sentence. Don't there exist cases where an infinite field has a finite characteristic? Or is there any way to prove Corollary 10 without following this line of reasoning?

  • $\begingroup$ An infinite field certainly can have finite characteristic, such as the algebraic closure $\widetilde{\mathbb F}_p$ or the simple transcendental extension $\mathbb F_p(t)$. I don’t know the context it appears in in this paper, perhaps their methods somehow can be adapted to these cases, or something. But on its own, this definitely sounds quite suspicious. $\endgroup$ Mar 18 '21 at 7:53
  • $\begingroup$ Yes I agree with you. Thank you for your comment. Perhaps someone familiar with counting complexity related to tensor-formula-related problems can provide any information over the correctness and the rigorous proof of the statement made by the authors? $\endgroup$
    – Conn-CaoYK
    Mar 18 '21 at 8:34
  • 2
    $\begingroup$ (In the full paper, the same claim is made as Corollary 4.6.) The more I think about it, it looks as an error. Presumably, the same argument shows that permanent of 0–1 matrices modulo $p$ reduces to $\mathrm{val}_F$ when $F$ has characteristic $p$, but this does not give #P-hardness (only $\oplus_pP$-hardness for odd $p$, and nothing much for $p=2$). $\endgroup$ Mar 18 '21 at 11:33
  • $\begingroup$ Thank you for your comments on the implications when the field is of odd prime characteristic. I didn't know the complexity of permanent of 0/1 matrices on such a field before. $\endgroup$
    – Conn-CaoYK
    Mar 18 '21 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.