4
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ 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... $\endgroup$ Dec 13, 2020 at 16:20
  • $\begingroup$ @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? $\endgroup$
    – User2021
    Sep 8, 2021 at 12:24
  • $\begingroup$ 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? $\endgroup$
    – Yonatan N
    Sep 9, 2021 at 1:27
  • $\begingroup$ @YonatanN Nothing specific. $\endgroup$
    – User2021
    Sep 9, 2021 at 5:45
  • $\begingroup$ 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"? $\endgroup$
    – Etsch
    Feb 14 at 19:57

1 Answer 1

-1
$\begingroup$

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 ?

$\endgroup$
3
  • $\begingroup$ Please read the question properly. We do not have a $P$ algorithm to distinguish. $\endgroup$
    – User2021
    Sep 8, 2021 at 18:54
  • $\begingroup$ 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 $\endgroup$
    – ULechine
    Sep 9, 2021 at 9:03
  • $\begingroup$ Please (I repeat) read the question and the comments properly. $\endgroup$
    – User2021
    Sep 9, 2021 at 9:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.