<p>An upper bound of <span class="math-container">$O(2^{n^{\epsilon}})$</span> <em>may</em> not be possible for any <span class="math-container">$\epsilon&lt;1$</span> unless the Exponential Time Hypothesis (ETH) is false, see</p>
<blockquote>
<p><em>Holger Dell, Thore Husfeldt, and Martin Wahlén</em>.</p>
<p>Exponential time complexity of the permanent and the Tutte polynomial.</p>
<p>Full paper at ECCC TR10-78. <a href="http://eccc.hpi-web.de/report/2010/078/" rel="nofollow noreferrer">http://eccc.hpi-web.de/report/2010/078/</a></p>
</blockquote>
<p>That is, if your embedding of the <span class="math-container">$n\times n$</span> permanent into a determinant of size <span class="math-container">$O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$</span> is fast enough, you could</p>
<ol>
<li><p>Transform a 3SAT-instance to a permanent as in the paper above</p>
</li>
<li><p>Transform the permanent to a determinant over the larger matrix</p>
</li>
<li><p>Compute the determinant to find the number of solutions to the
original 3SAT-instance.</p>
</li>
</ol>
<p>The running time for an <span class="math-container">$n$</span>-variate 3SAT instance would be <span class="math-container">$O(2^{n^{\epsilon'}})$</span> for some <span class="math-container">$\epsilon'&lt;1$</span> depending on <span class="math-container">$\epsilon$</span> if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.</p>

CC BY-SA 3.0
2011-11-14T07:14:03.483Z
2015-10-13T02:24:04.627Z
2020-06-17T09:38:08.363Z
Andreas Björklund
<p>Let $A$ be a given square matrix. 
Is there any evidence that beating <a href="http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf" rel="nofollow">quadratic lower bounds</a> for $B$ 
such that $\text{det}(B) = \text{per}(A)$ could be hard? </p>

<p>Is there any plausible conjecture which implies that 
proving lower bounds is difficult?
Is there any evidence that 
proving an $\Omega(n^{2+\epsilon})$ rows (or columns) lower bound 
for some $\epsilon &gt; 0$ is hard 
(e.g. equivalent to $\mathsf{VP} \ne \mathsf{VNP}$)? </p>

<p>Is there any plausible conjecture which implies that 
proving upper bounds is difficult?
Is there any evidence that 
proving an $O(2^{n^\epsilon})$ upper bound 
for some $\epsilon \in (0,1)$ is hard?</p>

CC BY-SA 3.0
2011-11-13T18:51:04.107Z
I think that this question could use a little more explanation. I believe I've figured out what you mean, but I'm not totally sure.
Peter Shor 
CC BY-SA 3.0
2011-11-14T00:49:59.067Z
Is there a reference for the  "quadratic lower bound for $B$ such that det(B) = per(A)" ?
Suresh Venkat
CC BY-SA 3.0
2011-11-14T01:02:03.030Z
@SureshVenkat Doesn't the following result imply a quadratic lower bound? http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf
v s
CC BY-SA 3.0
2011-11-14T01:26:58.553Z
Well that's my point. it would be useful to link to that in the question.
Suresh Venkat
CC BY-SA 3.0
2011-11-14T01:49:38.267Z
@SureshVenkat Oh Ok!
v s
CC BY-SA 3.0
2011-11-15T18:47:42.530Z
Isn't the first question like asking whether $SAT \notin DTIME(n^2)$ implies $P \not= NP$?
Markus Bläser
CC BY-SA 3.0
2011-11-15T20:26:44.077Z
@MarkusBläser Is it supposed to be $\mathsf{SAT} \notin \mathsf{DTIME}(n^{r})$ $\forall r \in \mathbb{R}_{+} \implies \mathsf{P} \neq \mathsf{NP}$?

I do not think so that is what I mean. What I mean is $B$ truly could need atleast $2^{\Omega(n)}$ rows and columns, however proving even an $n^{2 + \epsilon}$ bound would be as hard as or imply $\mathsf{VP} \ne \mathsf{VNP}$. Please refer to Andreas Bjorkland's answer below for the similar upper bound implication.
v s
CC BY-SA 3.0
2011-11-16T10:15:49.453Z
@v s The first statement of your comment is even an equivalence. Regarding the quadratic bound: What I mean is the following. Assume you can write the permanent as a projection of the determinant of a matrix a size $n^3 \times n^3$ and this is best possible. Then you can beat the quadratic lower bound and still VP = VNP. So I simply doubt that a modest improvement of the quadratic lower bound will tell you anything about VP and VNP.
Markus Bläser
CC BY-SA 3.0
2011-11-16T16:18:07.667Z
@MarkusBläser I dont think that is what I am implying in my statement. I am asking for an equivalence showing the difficulty of finding the possibility whether deciding an $n^{2+\epsilon}$ matrix exists is itself hard. Here you assume a cubic matrix exists. I am saying the procedure to find that itself could be hard.
v s
CC BY-SA 3.0
2011-11-16T17:31:10.000Z
I mean deciding whether a $n^{2+\epsilon}$ matrix is probably a better lower bound is itself hard*. So that leaves open the possibility of exponential lower bounds
v s
CC BY-SA 3.0
2015-10-12T05:00:03.233Z
@Kaveh There is no specific issue. First query of the post is not addressed in 4 years and that is why I brought to attention. And why are you changing titles I never touched with your own meaningless titles? I changed it back to state that was in before I touched. Please do not change to irrelevant titles. The original title by the author was damn good. what does it mean improving lower bound? This query is much more than that. He is asking whether superquadratic lower bound would mean VNP is not VP which is much much stronger and specific than your irrelevant title.
Turbo
CC BY-SA 3.0
2015-10-12T05:21:21.457Z
@kaveh I told you the same thing. Please do not change vs' original title which was better than yours. He can do the same edits with mine as to yours if he does not like mine ( something that you are unfairly suggesting here by putting your edits on top of vs' better title)
Turbo
CC BY-SA 3.0
2015-10-12T05:23:52.267Z
I like the title as vs put it. You rolled back my edits twice as well. I just rolld back to vs' original edit leaving the post as it was before my edit. It is you who are causing unnecessary edits
Turbo
CC BY-SA 3.0
2015-10-12T14:22:54.803Z
I have reverted to @Kaveh's edit, which I think improves the question.  I hope this ends the rollback war.
Lev Reyzin
CC BY-SA 3.0
2015-10-12T21:15:08.137Z
The title is no good (and cries for a meaning) as if you may have observed this is not about hardness of lower bound. the author specifically does not ask for hardness (such as NP completeness of improving lower bound). He specifically asks if $n^{2+\epsilon}$ lower bound itself gives $vnp\neq vp$ which kaveh's misinterpreted headline misses like an asteroid missing humankind everytime. This is on same level as superpolynomial lower bound at depth 3 implies superpolynomial general lower bound. I cannot believe the moderators cannot see this and the author has not been online for many years
Turbo
CC BY-SA 3.0
2015-10-13T02:17:19.563Z
@Turbo, I think you are reading the phrase "hardness" too narrowly. Google e.g. for "hardness amplification" or "lower bound amplification". In any case the constructive way to deal with the issue is not rolling back the whole edit because you disagree with the title, but to edit the title to improve it.
Kaveh
<cc.complexity-theory><lower-bounds><counting-complexity><algebraic-complexity><permanent>
Conditional results implying difficulty of improving upper/lower bounds for permanent
v s
# Conditional results implying difficulty of improving upper/lower bounds for permanent

(Asked by: username_0 on 2011-11-13)

Let $A$ be a given square matrix.
Is there any evidence that beating [quadratic lower bounds](http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf) for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?

Is there any plausible conjecture which implies that
proving lower bounds is difficult?
Is there any evidence that
proving an $\Omega(n^{2+\epsilon})$ rows (or columns) lower bound
for some $\epsilon > 0$ is hard
(e.g. equivalent to $\mathsf{VP} \ne \mathsf{VNP}$)?

Is there any plausible conjecture which implies that
proving upper bounds is difficult?
Is there any evidence that
proving an $O(2^{n^\epsilon})$ upper bound
for some $\epsilon \in (0,1)$ is hard?

**Tags:** cc.complexity-theory, lower-bounds, counting-complexity, algebraic-complexity, permanent
> **Comments:**
> **username_1**: I think that this question could use a little more explanation. I believe I've figured out what you mean, but I'm not totally sure.  
> **username_2**: Is there a reference for the  "quadratic lower bound for $B$ such that det(B) = per(A)" ?  
> **username_0**: @SureshVenkat Doesn't the following result imply a quadratic lower bound? http://pages.cs.wisc.edu/~jyc/papers/per-det.pdf  
> **username_2**: Well that's my point. it would be useful to link to that in the question.  
> **username_0**: @SureshVenkat Oh Ok!  
> **username_3**: Isn't the first question like asking whether $SAT \notin DTIME(n^2)$ implies $P \not= NP$?  
> **username_0**: @MarkusBläser Is it supposed to be $\mathsf{SAT} \notin \mathsf{DTIME}(n^{r})$ $\forall r \in \mathbb{R}_{+} \implies \mathsf{P} \neq \mathsf{NP}$?  I do not think so that is what I mean. What I mean is $B$ truly could need atleast $2^{\Omega(n)}$ rows and columns, however proving even an $n^{2 + \epsilon}$ bound would be as hard as or imply $\mathsf{VP} \ne \mathsf{VNP}$. Please refer to Andreas Bjorkland's answer below for the similar upper bound implication.  
> **username_3**: @v s The first statement of your comment is even an equivalence. Regarding the quadratic bound: What I mean is the following. Assume you can write the permanent as a projection of the determinant of a matrix a size $n^3 \times n^3$ and this is best possible. Then you can beat the quadratic lower bound and still VP = VNP. So I simply doubt that a modest improvement of the quadratic lower bound will tell you anything about VP and VNP.  
> **username_0**: @MarkusBläser I dont think that is what I am implying in my statement. I am asking for an equivalence showing the difficulty of finding the possibility whether deciding an $n^{2+\epsilon}$ matrix exists is itself hard. Here you assume a cubic matrix exists. I am saying the procedure to find that itself could be hard.  
> **username_0**: I mean deciding whether a $n^{2+\epsilon}$ matrix is probably a better lower bound is itself hard*. So that leaves open the possibility of exponential lower bounds  
> **username_4**: @Kaveh There is no specific issue. First query of the post is not addressed in 4 years and that is why I brought to attention. And why are you changing titles I never touched with your own meaningless titles? I changed it back to state that was in before I touched. Please do not change to irrelevant titles. The original title by the author was damn good. what does it mean improving lower bound? This query is much more than that. He is asking whether superquadratic lower bound would mean VNP is not VP which is much much stronger and specific than your irrelevant title.  
> **username_4**: @kaveh I told you the same thing. Please do not change vs' original title which was better than yours. He can do the same edits with mine as to yours if he does not like mine ( something that you are unfairly suggesting here by putting your edits on top of vs' better title)  
> **username_4**: I like the title as vs put it. You rolled back my edits twice as well. I just rolld back to vs' original edit leaving the post as it was before my edit. It is you who are causing unnecessary edits  
> **username_5**: I have reverted to @Kaveh's edit, which I think improves the question.  I hope this ends the rollback war.  
> **username_4**: The title is no good (and cries for a meaning) as if you may have observed this is not about hardness of lower bound. the author specifically does not ask for hardness (such as NP completeness of improving lower bound). He specifically asks if $n^{2+\epsilon}$ lower bound itself gives $vnp\neq vp$ which kaveh's misinterpreted headline misses like an asteroid missing humankind everytime. This is on same level as superpolynomial lower bound at depth 3 implies superpolynomial general lower bound. I cannot believe the moderators cannot see this and the author has not been online for many years  
> **username_6**: @Turbo, I think you are reading the phrase "hardness" too narrowly. Google e.g. for "hardness amplification" or "lower bound amplification". In any case the constructive way to deal with the issue is not rolling back the whole edit because you disagree with the title, but to edit the title to improve it.  

---

## 1 answers

### Answer by username_7 on 2011-11-14. Score: 15

An upper bound of $O(2^{n^{\epsilon}})$ *may* not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see

> *Holger Dell, Thore Husfeldt, and Martin Wahlén*.
>
> Exponential time complexity of the permanent and the Tutte polynomial.
>
> Full paper at ECCC TR10-78. <http://eccc.hpi-web.de/report/2010/078/>

That is, if your embedding of the $n\times n$ permanent into a determinant of size $O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$ is fast enough, you could

1. Transform a 3SAT-instance to a permanent as in the paper above
2. Transform the permanent to a determinant over the larger matrix
3. Compute the determinant to find the number of solutions to the
   original 3SAT-instance.

The running time for an $n$-variate 3SAT instance would be $O(2^{n^{\epsilon'}})$ for some $\epsilon'<1$ depending on $\epsilon$ if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.


---

