0
$\begingroup$

Will every complexity class contain infinite number of problems?

If they do not, do common complexity classes (e.g. P,NP,PSPACE,EXPTIME,EXPSPACE etc.) contain infinite number of problems?

2 Answers 2

3

I believe "complexity class" is a term of art, and does not refer to anything more specific than just some set of problems that might possess an interesting property. If that is so, then one could make a "complexity class" that contained a finite number of problems.

All complexity classes of interest will be infinite, because for any finite "complexity class" $\mathcal C$, there is an algorithm to solve problems from $\mathcal C$ in constant time. This includes the important classes that you mentioned.

2

There is no formal definition for "Complexity class", so in theory you can always claim that some specific finite set of languages is a "complexity class".

However, every real-life complexity class is infinite, including all the classes you mentioned. Usually the following trick works: If $L\in C$ for some class $C$, so will $\$^{n}\cdot L$ (which means "the words in L with exactly $n$ times the symbol $\$ before them") where $\$ is not a symbol used in the language $L$ (we can also do similar trick with binary alphabet).

So, for every $n$ we get a language $\$^n\cdot L$ in $C$ and so $C$ is infinite.