<p>Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)?</p>

<p>Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly version of P)?</p>

<p>I could not find any consequences from quick search on google (except for a result by Jin Cai on #P, EXP and BPTIME) and Valiant's original hypothesis only says VP is not VNP.</p>

<p>It could be that permanent has a quasipoly algorithm or circuit. Is there any arguments for and against this?</p>

CC BY-SA 3.0
2017-02-16T18:04:32.663Z
You would get a quasipoly algorithm for any problem in PH. Isn't that surprising enough?
Sasho Nikolov
CC BY-SA 3.0
2017-02-16T18:16:40.120Z
@SashoNikolov what if even they are all in quasipoly it does not disturb the complexity landscape? It could still be P=BPP right?
Turbo
CC BY-SA 3.0
2017-02-16T18:51:28.390Z
A quasipoly algorithm for any problem in PH to me seems like a huge disturbance in the complexity landscape
Sasho Nikolov
CC BY-SA 3.0
2017-02-16T20:07:39.997Z
@SashoNikolov sorry by disturbance I mean any violation to relative ordering of classes (like collapse results or P \neq BPP - any thing unexpected at all other than PH in Qpoly)?
Turbo
CC BY-SA 3.0
2017-02-17T02:08:43.080Z
See this answer http://cstheory.stackexchange.com/a/36764/4896
Sasho Nikolov
CC BY-SA 3.0
2017-02-17T03:41:24.267Z
@SashoNikolov oh I see some other implication outside PH.
Turbo
<cc.complexity-theory><complexity-classes><big-picture><permanent><hierarchy-theorems>
Permanent in Bounded error Quasi Poly time
Turbo
# Permanent in Bounded error Quasi Poly time

(Asked by: username_0 on 2017-02-16)

Is there any consequence to complexity theory if Permanent has a BQP (classical quasipoly version of BPP)?

Is there any consequence to complexity theory if Permanent has a QP (classical quasipoly version of P)?

I could not find any consequences from quick search on google (except for a result by Jin Cai on #P, EXP and BPTIME) and Valiant's original hypothesis only says VP is not VNP.

It could be that permanent has a quasipoly algorithm or circuit. Is there any arguments for and against this?

**Tags:** cc.complexity-theory, complexity-classes, big-picture, permanent, hierarchy-theorems

> **Comments:**
> **username_1**: You would get a quasipoly algorithm for any problem in PH. Isn't that surprising enough?  
> **username_0**: @SashoNikolov what if even they are all in quasipoly it does not disturb the complexity landscape? It could still be P=BPP right?  
> **username_1**: A quasipoly algorithm for any problem in PH to me seems like a huge disturbance in the complexity landscape  
> **username_0**: @SashoNikolov sorry by disturbance I mean any violation to relative ordering of classes (like collapse results or P \neq BPP - any thing unexpected at all other than PH in Qpoly)?  
> **username_1**: See this answer http://cstheory.stackexchange.com/a/36764/4896  
> **username_0**: @SashoNikolov oh I see some other implication outside PH.  

---

## 0 answers

