The various complexity classes usually taught and studied ($P$, $NP$ $co-NP$, EXP, NSPACE etc) are usually defined using Turing Machines as the preferred model of computation.

Are these sets of decision problems (complexity classes) independent of the model of computation used?

  • $\begingroup$ It depends on the model of computation... but many of these classes are quite robust. $\endgroup$ – Yuval Filmus Sep 17 '19 at 14:16

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.