120:(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.
92:
if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class.
108:
of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement.
426:
167:
404:
377:
350:
323:
298:
271:
242:
215:
17:
85:
the complement of the complexity class itself as a set of problems, which would contain a great deal more problems.
155:
define their probabilities with one-sided error, and so are not (currently known to be) closed under complement.
59:
37:
51:(a number which is not prime). Here the domain of the complement is the set of all integers exceeding one.
105:
396:
Complexity and
Approximation: Combinatorial Optimization Problems and Their Approximability Properties
101:, are believed to be distinct from their complement classes (although this has not been proven).
94:
158:
Some of the most surprising complexity results shown to date showed that the complexity classes
400:
394:
373:
346:
340:
319:
294:
288:
267:
238:
237:, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19,
211:
205:
166:
are in fact closed under complement, whereas before it was widely believed they were not (see
367:
232:
184:
128:
124:
66:
55:
48:
25:
318:, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134,
62:, meaning it "undoes itself", or the complement of the complement is the original problem.
163:
159:
148:
136:
98:
36:
answers. Equivalently, if we define decision problems as sets of finite strings, then the
176:
73:, which is the set of complements of every problem in the class. If a class is called
420:
44:
345:, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113,
259:
58:
from every problem to its complement problem. The complement operation is an
147:
instances are closed under complement. In contrast, classes such as
293:, Texts in Computer Science, Springer, Exercise 9.10, p. 287,
369:
Complexity Theory: Exploring the Limits of
Efficient Algorithms
132:
40:
of this set over some fixed domain is its complement problem.
43:
For example, one important problem is whether a number is a
170:). The latter has become less surprising now that we know
47:. Its complement is to determine whether a number is a
342:
Introduction to
Circuit Complexity: A Uniform Approach
139:
which are defined symmetrically with regards to their
28:
is the decision problem resulting from reversing the
207:Encyclopedic Dictionary of Mathematics, Volume 1
65:One can generalize this to the complement of a
314:Bovet, Daniele; Crescenzi, Pierluigi (1994),
8:
77:, its complement is conventionally labelled
123:Similarly, probabilistic classes such as
316:Introduction to the Theory of Complexity
234:Theory of Linear and Integer Programming
266:, Texts in Computer Science, Springer,
196:
187:for itself is closed under complement.
112:Every deterministic complexity class (
97:, many important classes, especially
7:
264:Computability and Complexity Theory
180:, which is a deterministic class.
14:
366:Pruim, R.; Wegener, Ingo (2005),
427:Computational complexity theory
18:computational complexity theory
290:Elements of Computation Theory
1:
231:Schrijver, Alexander (1998),
168:Immerman–Szelepcsényi theorem
443:
393:Ausiello, Giorgio (1999),
339:Vollmer, Heribert (1999),
210:, MIT Press, p. 269,
399:, Springer, p. 189,
372:, Springer, p. 66,
287:Singh, Arindama (2009),
90:closed under complement
88:A class is said to be
81:. Notice that this is
183:Every class which is
204:ItĂ´, Kiyosi (1993),
95:many-one reductions
434:
411:
409:
390:
384:
382:
363:
357:
355:
336:
330:
328:
311:
305:
303:
284:
278:
276:
255:
249:
247:
228:
222:
220:
201:
71:complement class
67:complexity class
56:Turing reduction
49:composite number
26:decision problem
442:
441:
437:
436:
435:
433:
432:
431:
417:
416:
415:
414:
407:
392:
391:
387:
380:
365:
364:
360:
353:
338:
337:
333:
326:
313:
312:
308:
301:
286:
285:
281:
274:
260:Selman, Alan L.
258:Homer, Steven;
257:
256:
252:
245:
230:
229:
225:
218:
203:
202:
198:
193:
93:However, under
12:
11:
5:
440:
438:
430:
429:
419:
418:
413:
412:
405:
385:
378:
358:
351:
331:
324:
306:
299:
279:
272:
250:
243:
223:
216:
195:
194:
192:
189:
13:
10:
9:
6:
4:
3:
2:
439:
428:
425:
424:
422:
408:
406:9783540654315
402:
398:
397:
389:
386:
381:
379:9783540274773
375:
371:
370:
362:
359:
354:
352:9783540643104
348:
344:
343:
335:
332:
327:
325:9780139153808
321:
317:
310:
307:
302:
300:9781848824973
296:
292:
291:
283:
280:
275:
273:9781461406815
269:
265:
261:
254:
251:
246:
244:9780471982326
240:
236:
235:
227:
224:
219:
217:9780262590204
213:
209:
208:
200:
197:
190:
188:
186:
181:
179:
178:
173:
169:
165:
161:
156:
154:
150:
146:
142:
138:
134:
130:
126:
121:
119:
115:
110:
107:
102:
100:
96:
91:
86:
84:
80:
76:
72:
69:, called the
68:
63:
61:
57:
52:
50:
46:
41:
39:
35:
31:
27:
23:
19:
395:
388:
368:
361:
341:
334:
315:
309:
289:
282:
263:
253:
233:
226:
206:
199:
182:
175:
171:
157:
152:
144:
140:
122:
117:
113:
111:
103:
89:
87:
82:
78:
74:
70:
64:
53:
45:prime number
42:
33:
29:
21:
15:
54:There is a
191:References
60:involution
38:complement
22:complement
421:Category
262:(2011),
116:(f(n)),
174:equals
106:closure
403:
376:
349:
322:
297:
270:
241:
214:
114:DSPACE
20:, the
153:co-RP
118:DTIME
24:of a
401:ISBN
374:ISBN
347:ISBN
320:ISBN
295:ISBN
268:ISBN
239:ISBN
212:ISBN
162:and
151:and
143:and
104:The
79:co-C
32:and
185:low
141:yes
135:or
133:BQP
129:ZPP
125:BPP
83:not
30:yes
16:In
423::
172:SL
164:SL
160:NL
149:RP
145:no
137:PP
131:,
127:,
99:NP
34:no
410:.
383:.
356:.
329:.
304:.
277:.
248:.
221:.
177:L
75:C
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.