5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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$
    – Emil Jeřábek
    Commented Mar 18, 2021 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
    Commented Mar 18, 2021 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$
    – Emil Jeřábek
    Commented Mar 18, 2021 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
    Commented Mar 18, 2021 at 12:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.