<p>For the second question, If you have an algorithm in <span class="math-container">$P$</span> which can distinguish between those <span class="math-container">$k$</span> values, then you have an algorithm in <span class="math-container">$P$</span> for the 0-1 permanent (by combining the two algorithms) which is <span class="math-container">$\#P$</span> complete. Therefore <span class="math-container">$\#P=P$</span>, since <span class="math-container">$BPP$</span> is in <span class="math-container">$\#P$</span> we have that <span class="math-container">$BPP=P$</span>.</p>
<p>Unless i'm missing something ?</p>

CC BY-SA 4.0
2021-09-08T18:54:58.430Z
Please read the question properly. We do not have a $P$ algorithm to distinguish.
User2021
CC BY-SA 4.0
2021-09-09T09:03:36.493Z
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
CC BY-SA 4.0
2021-09-09T09:52:59.323Z
Please (I repeat) read the question and the comments properly.
User2021
CC BY-SA 4.0
2021-09-08T14:33:46.543Z
2021-09-08T14:33:46.543Z
ULechine
<p>We are given a matrix <span class="math-container">$M$</span> with <span class="math-container">$0/1$</span> entries and the matrix is square of <span class="math-container">$n$</span> dimensions. We are given two integers <span class="math-container">$a$</span> and <span class="math-container">$b$</span> with promise one of the values is the permanent.</p>
<p>Is there a faster than <span class="math-container">$2^{\Omega(n)}$</span> algorithm to identify the correct permanent of the two values of <span class="math-container">$a$</span> and <span class="math-container">$b$</span> (output <span class="math-container">$0$</span> means <span class="math-container">$a$</span> is correct and putput <span class="math-container">$1$</span> means <span class="math-container">$b$</span> is correct) and is there a complexity class for this problem?</p>
<p>We might assume the lower <span class="math-container">$n-n^\alpha$</span> bits of <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are identical at an <span class="math-container">$\alpha\in(0,1)$</span>.</p>
<hr />
<p>How about if we have a <span class="math-container">$P$</span> algorithm which always spits</p>
<ol>
<li><p><span class="math-container">$k=O(1)$</span> values one of which is the permanent?</p>
</li>
<li><p><span class="math-container">$k=poly(n)$</span> values one of which is the permanent?</p>
</li>
</ol>
<p>In these case if we assume the outputs <span class="math-container">$a_1,\dots,a_k$</span> have an equal chance of being correct then we can pick one index (say always <span class="math-container">$a_1$</span>) and be successful <span class="math-container">$1/O(1)$</span> to <span class="math-container">$1/poly(n)$</span> of the times and there is an <span class="math-container">$RTIME$</span> algorithm by Lipton. Is there any way to convert the algorithm to a deterministic algorithm without utilizing <span class="math-container">$P=BPP$</span> approach at least if <span class="math-container">$k=O(1)$</span>?</p>

CC BY-SA 4.0
2020-12-13T16:20:39.087Z
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
CC BY-SA 4.0
2021-09-08T12:24:31.857Z
@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
CC BY-SA 4.0
2021-09-09T01:27:11.260Z
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
CC BY-SA 4.0
2021-09-09T05:45:27.893Z
@YonatanN Nothing specific.
User2021
CC BY-SA 4.0
2022-02-14T19:57:43.813Z
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
CC BY-SA 4.0
2022-02-27T15:21:36.793Z
@Etsch It is interesting enough for a new question. Can you post one?
User2021
<permanent><promise-problems>
Distinguishing permanent from false value
User2021
# Distinguishing permanent from false value

(Asked by: username_0 on 2020-12-13)

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

**Tags:** permanent, promise-problems

> **Comments:**
> **username_1**: 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...  
> **username_0**: @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?  
> **username_2**: 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?  
> **username_0**: @YonatanN Nothing specific.  
> **username_3**: 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"?  
> **username_0**: @username_3 It is interesting enough for a new question. Can you post one?  

---

## 1 answers

### Answer by username_4 on 2021-09-08. Score: -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 ?

> **Comments:**
> **username_0**: Please read the question properly. We do not have a $P$ algorithm to distinguish.  
> **username_4**: 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  
> **username_0**: Please (I repeat) read the question and the comments properly.  

---

