Aho says $D(f)=O(N(f)N(\overline f))$ where $D(f)$ is deterministic communication complexity and $N(f)$ is non-deterministic version.

Do we know $PP(f)=\Omega(2^{(N(f)N(\overline f))^{O(1)}})$ or $PP(f)=O((N(f)N(\overline f))^{O(1)})$?

  • $\begingroup$ Where does Aho say that? ​ ​ $\endgroup$ – user6973 Jan 8 '18 at 3:56
  • $\begingroup$ @RickyDemer corrected $\endgroup$ – T.... Jan 8 '18 at 14:41

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.