Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel.

How does one capture that in a proper formalism? Is there some literature on it already? Would it be true that such a class would be a superset of BQP?

  • $\begingroup$ "exponentially many processors working in parallel" And with unbounded time and space requirements on each processor? $\endgroup$ – dkaeae Jul 25 '19 at 15:28
  • $\begingroup$ @dkaeae polynomial time and space requirements on each processor $\endgroup$ – Jsevillamol Jul 25 '19 at 16:12
  • 1
    $\begingroup$ Well Nick's Class $NC^i$ concerns polynomially many processors in parallel with shared memory, it stratifies $P$ (conjectured to reach $P$). I would think the natural thing to generalize is non-deterministic NC. See Caussinus-MacKinzie and references form there. $\endgroup$ – Algeboy Jul 25 '19 at 19:45

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.