I am currently trying to learn some more about complexity classes. I found this exercise but I cannot find a proper solution to this exercise:

Principia matematica

I know this is in NP, can I also say it is in P? If that's the case how could I formally prove it?

  • $\begingroup$ The language is in RE, but definitely not in NP or P. To proof that something is in RE you just have to show that there is an algorithm that lists all provable theorems (under the PMs axioms). $\endgroup$
    – plshelp
    Jul 8, 2022 at 16:02
  • $\begingroup$ @plshelp, wait, I think the question talks only about the set of theorems from the book, i.e. the language is finite. $\endgroup$
    – Dmitry
    Jul 8, 2022 at 21:07
  • $\begingroup$ Ooff, then the language is regular, because you can just write a regular expression that matches all words. And regular languages are $\subset P$. $\endgroup$
    – plshelp
    Jul 8, 2022 at 23:31
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources! $\endgroup$
    – D.W.
    Jul 9, 2022 at 18:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.