# Distinguishing permanent from false value

We are given a matrix $$M$$ with $$0/1$$ entries and the matrix is square of $$n$$ dimensions. We are given two integers $$a$$ and $$b$$ with promise one of the values is the permanent.

Is there a faster than $$2^{\Omega(n)}$$ algorithm to identify the correct permanent of the two values of $$a$$ and $$b$$ (output $$0$$ means $$a$$ is correct and putput $$1$$ means $$b$$ is correct) and is there a complexity class for this problem?

We might assume the lower $$n-n^\alpha$$ bits of $$a$$ and $$b$$ are identical at an $$\alpha\in(0,1)$$.

How about if we have a $$P$$ algorithm which always spits

1. $$k=O(1)$$ values one of which is the permanent?

2. $$k=poly(n)$$ values one of which is the permanent?

In these case if we assume the outputs $$a_1,\dots,a_k$$ have an equal chance of being correct then we can pick one index (say always $$a_1$$) and be successful $$1/O(1)$$ to $$1/poly(n)$$ of the times and there is an $$RTIME$$ algorithm by Lipton. Is there any way to convert the algorithm to a deterministic algorithm without utilizing $$P=BPP$$ approach at least if $$k=O(1)$$?

• If you consider algorithms given by algebraic decision trees, then your problem is not significantly easier than just computing the permanent (cstheory.stackexchange.com/q/115/129). For 0-1 matrices and computations on Turing machines there might be other tricks... Dec 13, 2020 at 16:20
• @JoshuaGrochow How about if we have a $P$ algorithm which always spits $k=O(1)$ values one of which is the permanent? In this case if we assume the outputs $a_1,\dots,a_k$ have an equal chance of being correct then we can pick one and be successful $1/O(1)$ of the times and there an $RTIME$ algorithm by Lipton. Is there any way to convert to a deterministic algorithm? Sep 8, 2021 at 12:24
• A polynomial-time algorithm $A$ for the first problem would seem to place permanents in (some functional equivalent of) the second layer of the polynomial hierarchy, as computing the permanent would be equivalent to asking for an $a$ such that for all $b$, $A(M,a,b) = a$. This combined with Toda's theorem should lead to a collapse of $PH$. I'm guessing this is why you're asking specifically about subexponential-time algorithms rather than polynomial-time? Sep 9, 2021 at 1:27
• @YonatanN Nothing specific. Sep 9, 2021 at 5:45
• The FPRAS algorithm of Jerrum et al. outputs an upper and lower bound for the permanent in polynomial time for a 0/1 matrix. Couldn't this be used to solve the problem if the two integers a and b are '"different enough"? Feb 14 at 19:57

For the second question, If you have an algorithm in $$P$$ which can distinguish between those $$k$$ values, then you have an algorithm in $$P$$ for the 0-1 permanent (by combining the two algorithms) which is $$\#P$$ complete. Therefore $$\#P=P$$, since $$BPP$$ is in $$\#P$$ we have that $$BPP=P$$.
• Please read the question properly. We do not have a $P$ algorithm to distinguish. Sep 8, 2021 at 18:54