# Categorising problems into complexity classes

Am I correct in saying that there are two ways to categorise a problem in complexity theory:

• Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-class. If not, then we can put it into EXP.

• Provide a reduction that this problem is no hard than another problem, to which we know the complexity class for.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class? I'm guessing it would be in the class of problems which cannot be solved until we find an algorithm.

• There are algorithms whose running time is more than exponential. – Yuval Filmus Jun 20 at 13:15
• @YuvalFilmus understood. Is the rationale correct though? "We categorise problems based on the best known algorithm or their relation to other problems who we know the complexity classes for" ? – WeCanBeFriends Jun 20 at 20:04
• Yes, this is a nice summary. – Yuval Filmus Jun 20 at 20:04
• @YuvalFilmus got it thank you – WeCanBeFriends Jun 20 at 20:06

Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $$C$$ you have found for it. For instance, if you have a problem $$P$$ and show it is reducible to a complete problem in $$\mathsf{PP}$$, then you are not done yet. For all we know, $$P$$ could be $$\mathsf{PP}$$-complete, but it could also be in $$\mathsf{NP}$$, or $$\mathsf{BPP}$$, etc. Therefore, to finish classifying $$P$$, you should be able to find a class it is complete for—if possible; after all, there are classes which are not closed under (poly-time many-one) reductions—, or provide some good evidence why it could not be in a class which is known (or conjectured) to be strictly below $$C$$.
Assuming your problem is decidable, the "default" complexity class is $$\mathsf{R}$$, the class of recursive languages. Improving on this is only possible by producing an algorithm whose time complexity you can prove or, alternatively, proving a reduction to some other problem for which this is the case; that is, essentially what you wrote in your question. There is no such thing as a "class of problems which cannot be solved until we find an algorithm" in complexity theory; that would be the domain of computability theory (i.e., problems which are not known to be decidable).