Complement (complexity): Difference between revisions

Revision as of 06:48, 26 May 2007

Revision as of 19:52, 15 October 2007

Line 1:

{{Unreferenced|article|date=February 2007}}

In [[computational complexity theory]], the '''complement''' of a [[decision problem]] is the decision problem resulting from reversing the ''yes'' and ''no'' answers. Equivalently, if we define decision problems as sets of finite strings, then the [[complement (set theory)|complement]] of this set over some fixed ___domain is its complement problem.