-4
$\begingroup$

I saw some proof but I didn't understood it, any simple one?

$\endgroup$
2
  • 2
    $\begingroup$ Do you understand the time hierarchy theorem? $\endgroup$ – Dmitry Feb 10 at 21:34
  • $\begingroup$ Thanks man! @Dmitry $\endgroup$ – ChaosPredictor Feb 11 at 6:19
1
$\begingroup$

Look at the time hierarchy theorem for an explanation. In particular, we know (using this theorem) that $P\subsetneq E\subsetneq EXP\subsetneq R$, and we could have added a lot more complexity classes in between them.

$\endgroup$
1
  • $\begingroup$ Thanks, I'll check this theorem $\endgroup$ – ChaosPredictor Feb 11 at 6:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.