5

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)$?

User2021
  • 93
  • 6
  • 2
    If you consider algorithms given by algebraic decision trees, then your problem is not significantly easier than just computing the permanent (https://cstheory.stackexchange.com/q/115/129). For 0-1 matrices and computations on Turing machines there might be other tricks... – Joshua Grochow Dec 13 '20 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? – User2021 Sep 08 '21 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? – Yonatan N Sep 09 '21 at 01:27
  • @YonatanN Nothing specific. – User2021 Sep 09 '21 at 05: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"? – Etsch Feb 14 '22 at 19:57
  • @Etsch It is interesting enough for a new question. Can you post one? – User2021 Feb 27 '22 at 15:21

1 Answers1

-1

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$.

Unless i'm missing something ?

ULechine
  • 149
  • 9
  • Please read the question properly. We do not have a $P$ algorithm to distinguish. – User2021 Sep 08 '21 at 18:54
  • I'm saying if you were to have a deterministic algorithm, then you'd prove P=BPP. Therefore there is no way to get a deterministic algorithm for this without proving/relying on the fact that P=BPP – ULechine Sep 09 '21 at 09:03
  • Please (I repeat) read the question and the comments properly. – User2021 Sep 09 '21 at 09:52