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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Complexity classes and number of problems

I know that almost all of complexity classes that have some significance have infinite number of decision problems.

Then what about complete area of these complexity classes? I know that the concept of complete is somewhat artificial, as it depends on some reduction processes.

So, for example, will NP-complete contain infinite number of problems?


share|cite|improve this question

marked as duplicate by MJD, LVK, tomasz, sdcvvc, William Aug 29 '12 at 21:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

There are certainly infinitely many NP-complete problems; for example, determining whether a graph is $k$-colorable is NP-complete for any $k \geq 3$. I suspect that you could come up with similarly trivial examples for just about any complexity class... – Micah May 20 '12 at 4:32
up vote 1 down vote accepted

The class of $\mathcal{NP}$-complete problems is infinite, as are all the complexity classes that are interesting, because for any finite "complexity class" $\mathcal C$, there is an algorithm to solve problems from $\mathcal C$ in constant time.

share|cite|improve this answer

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