# To what complexity class does this language belongs?

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:

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?

• 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). Jul 8, 2022 at 16:02
• @plshelp, wait, I think the question talks only about the set of theorems from the book, i.e. the language is finite. Jul 8, 2022 at 21:07
• Ooff, then the language is regular, because you can just write a regular expression that matches all words. And regular languages are $\subset P$. Jul 8, 2022 at 23:31
• 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!
– D.W.
Jul 9, 2022 at 18:30