Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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