8
$\begingroup$

Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as inputs).

You can evaluate $C$ in polynomial time (in the size of $C$), hence $C$ does only have polynomially bounded degree and exponentially bounded coefficients. Is the following problem $NP$-hard or even $NP$-complete?

Given $n$ and $C$. Does $C$ compute the permanent of all $n\times n$ integer-matrices?

Note: $n$ and $C$ are both input parameters, none is fixed.

The permanent of a matrix is similar to the determinant of a matrix (both are polynomials), but it is conjectured that it takes much more time than computing the determinant since it is #$P$-hard: https://en.wikipedia.org/wiki/Computing_the_permanent

I do not know how to start in order to obtain a reduction that would prove this.

$\endgroup$
6
  • 1
    $\begingroup$ This is unlikely to be NP-hard because it can be solved using polynomial identity testing and the downward self-reducibility of the permanent (Laplace expansion). Can you give your motivation for this problem / why you are interested in it? $\endgroup$ Commented Feb 1, 2023 at 22:25
  • 1
    $\begingroup$ The motivation was to find out more about NP-hardness of the permanent and circuit complexity. Could you expand on the idea of how you would solve this with polynomial identity testing? Would you then have randomized polynomial time complexity for this problem? $\endgroup$
    – user67795
    Commented Feb 1, 2023 at 22:43
  • $\begingroup$ Just to be clear, the problem has two input parameters, $n$ and $C$. $n$ is not fixed at all. But I probably am not seeing what you mean .. $\endgroup$
    – user67795
    Commented Feb 1, 2023 at 22:58
  • 1
    $\begingroup$ @Turbo: Yes it is a natural problem; that's not why I was asking. And yes, Mulmuley gave a nice GCT-related proof of this - see my answer. $\endgroup$ Commented Feb 1, 2023 at 23:15
  • 2
    $\begingroup$ @questionmaster: I'd suggest changing the title to be a little more descriptive, e.g. "Is it NP-hard to check whether a given algebraic circuit computes permanent?" $\endgroup$ Commented Feb 2, 2023 at 0:37

1 Answer 1

10
$\begingroup$

This is unlikely to be NP-complete, as it can be solved in coRP, using a few calls to PIT. (It follows that this problem is not NP-complete unless $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{PH} = \mathsf{BPP}$.)

I know of two ways to do this:

(1) Using the downward-self-reducibility of the permanent. (From Kabanets-Impagliazzo.) This goes as follows. The Laplace expansion of $perm_n(X)$ is $perm_n(X) = \sum_{i=1}^n x_{1i} perm_{n-1}(X(\hat{1}|\hat{i}))$, where the latter notation means the $(n-1) \times (n-1)$ submatrix that results from removing the first row and the $i$-th column. Next, if $C$ computes the permanent of an $n \times n$ matrix $X$, then $C(\begin{bmatrix} X' & 0_{n \times 1} \\ 0_{1 \times n} & 1 \end{bmatrix}) = perm_{n-1}(X')$. Let us denote this circuit, which has $(n-1)^2$ inputs, as $C_{n-1}$. Then we check the polynomial identity

$C(X) = \sum_{i=1}^n x_{1i} C_{n-1}(X(\hat{1} | \hat{i})$

Then you iterate this for $C_{n-1}$ and so on. That is $n$ polynomial identity tests in total, each of which can be solved in $\mathsf{coRP}$ by the usual algorithm (plug in random values and evaluate).

(2) Using the characterization of the permanent by its symmetries (from Mulmuley, "Explicit proofs and the flip", Prop 7.1). That is, the permanent is the unique polynomial $f(X)$ in $n^2$ variables such that (1) $f(Id)=1$ and (2) $f(P X P^T) = f(X)$ for all permutation matrices $P$, and (3) $f(DXD')=\mu(D,D')f(X)$ for all diagonal matrices $D,D'$, where $\mu(D,D')$ is the product of all their diagonal entries. Since the group of permutation matrices is generated by just two elements, corresponding to the permutations $(12)$ and $(1,2,3,\dotsc,n)$, say, we need only check those two. Then we use an idea similar to the above, as follows. Given a circuit $C(X)$, and a permutation $\pi \in S_n$, let $C_{\pi}$ denote the circuit you get by first permuting the variables $X$ to $P_{\pi} X P_{\pi}^T$ (that is, you send $x_{ij}$ to $x_{\pi(i), \pi(j)}$), and then applying $C$. Then we check that $C(Id)=1$, and we use PIT to check that $C(X) = C_{\pi}(X)$ for $\pi \in \{(12), (1,2,3,\dotsc,n)\}$.

To check the condition about diagonal matrices, we introduce $2n$ new variables corresponding to the entries of those diagonal matrices, and then check the polynomial identity $C(DXD') = \mu(D,D')C(X)$.

$\endgroup$
4
  • 2
    $\begingroup$ So, you do not even need the assumption that the degree of $C$ is polynomially bounded, PIT in coNP works for arbitrary circuits. $\endgroup$ Commented Feb 2, 2023 at 6:53
  • $\begingroup$ @Joshuagrochow isn't the first test actually in coRL or so since we only select random numbers and evaluating poly degree circuits? $\endgroup$
    – Turbo
    Commented Feb 2, 2023 at 14:11
  • $\begingroup$ @Turbo: To get it into coRL you probably have to use the same tricks Emil was referring to (eg from Ibarra-Moran, IIRC) that make the test work for unbounded-degree circuits. Namely, take the circuit modulo a bunch of small numbers and do the test there. I'd have to think a little carefully about it, but probably? But anyway, since the question was about NP-hardness, a coRP upper bound is already enough to make NP-hardness unlikely. $\endgroup$ Commented Feb 2, 2023 at 16:06
  • $\begingroup$ @JoshuaGrochow but an RL bound derandomizes by Nisan's result RL is in SC which makes the problem exciting and might be useful in GCT. $\endgroup$
    – Turbo
    Commented Feb 2, 2023 at 17:08

Your Answer

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