0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You would get a quasipoly algorithm for any problem in PH. Isn't that surprising enough? $\endgroup$ – Sasho Nikolov Feb 16 '17 at 18:04
  • $\begingroup$ @SashoNikolov what if even they are all in quasipoly it does not disturb the complexity landscape? It could still be P=BPP right? $\endgroup$ – Turbo Feb 16 '17 at 18:16
  • $\begingroup$ A quasipoly algorithm for any problem in PH to me seems like a huge disturbance in the complexity landscape $\endgroup$ – Sasho Nikolov Feb 16 '17 at 18:51
  • $\begingroup$ @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)? $\endgroup$ – Turbo Feb 16 '17 at 20:07
  • $\begingroup$ See this answer cstheory.stackexchange.com/a/36764/4896 $\endgroup$ – Sasho Nikolov Feb 17 '17 at 2:08

Your Answer

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

Browse other questions tagged or ask your own question.