Content deleted Content added
m robot Adding: pl:Dopełnienie (teoria złożoności) |
Woohookitty (talk | contribs) m WikiCleaner 0.98 - Repairing link to disambiguation page - You can help! |
||
Line 4:
For example, one important problem is whether a number is a [[prime number]]. Its complement is to determine whether a number is a [[composite number]] (a number which is not prime). Here the ___domain of the complement is the set of all integers exceeding one.
There is a [[Turing reduction]] from every problem to its complement problem. The complement operation is an [[Involution (mathematics)|involution]], meaning it "undoes itself", or the complement of the complement is the original problem.
We can generalize this to the complement of a [[complexity class]], called the '''complement class''', which is the set of complements of every problem in the class. If a class is called '''C''', its complement is conventionally labelled '''co-C'''. Notice that this is ''not'' the complement of the complexity class itself as a set of problems, which would contain a great deal more problems.
| |||