221:). A simpler proof of this based on left-sets was given by Ogihara and Watanabe in 1991. Mahaney's argument does not actually require the sparse language to be in NP (because the existence of an NP-hard sparse set implies the existence of an NP-complete sparse set), so there is a sparse
316:
135:
357:
Jin-Yi Cai. Lecture 11: P=poly, Sparse Sets, and
Mahaney's Theorem. CS 810: Introduction to Complexity Theory. The University of Wisconsin–Madison. September 18, 2003 (PDF)
524:
277:
420:
412:
175:
17:
519:
29:
393:
M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets.
492:
321:
In 1999, Jin-Yi Cai and D. Sivakumar, building on work by
Ogihara, showed that if there exists a sparse
85:
are sparse. An example of a nontrivial sparse language is the set of binary strings containing exactly
73:, and if a language only contains polynomially many of these, then the proportion of strings of length
482:
218:
101:
98:
33:
460:
435:
Juris
Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME.
456:
451:
Jin-Yi Cai and D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of
Hartmanis.
416:
380:
S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and
Hartmanis.
263:
55:
488:
247:
193:
50:
25:
356:
499:
336:
330:
267:
241:
186:
159:
82:
513:
478:
504:
48:. They are used primarily in the study of the relationship of the complexity class
203:
440:
322:
41:
464:
222:
168:
311:{\displaystyle {\textbf {NP}}\subseteq {\textbf {P}}/{\text{poly}}}
202:. Mahaney used this to show in 1982 that if any sparse language is
407:
Balcázar, JosĂ© Luis; DĂaz, Josep; GabarrĂł, Joaquim (1990).
162:, since these have at most one string of any one length.
274:-complete language to a sparse language if and only if
185:
Fortune showed in 1979 that if any sparse language is
280:
104:
310:
129:
121:
108:
69:because there are a total of 2 strings of length
251:if and only if there exist sparse languages in
138:strings in the language, which is bounded by
8:
367:S. Fortune. A note on sparse complete sets.
36:, counting the number of strings of length
439:, volume 65, issue 2/3, pp.158–181. 1985.
303:
298:
292:
291:
282:
281:
279:
146:Relationships to other complexity classes
120:
107:
105:
103:
77:that it contains rapidly goes to zero as
455:, volume 58, issue 2, pp.280–296. 1999.
453:Journal of Computer and System Sciences
382:Journal of Computer and System Sciences
349:
371:, volume 8, issue 3, pp.431–433. 1979.
7:
293:
283:
112:
58:of all sparse languages is called
14:
40:in the language, is bounded by a
493:Sparse Sets (Tribute to Mahaney)
270:from Mahaney's theorem) from an
176:polynomial-time Turing reduction
525:Computational complexity theory
130:{\displaystyle {\binom {n}{k}}}
18:computational complexity theory
167:Although not all languages in
1:
483:Favorite Theorems: Small Sets
397:volume 20, pp.471–483. 1991.
65:Sparse languages are called
182:/poly to a sparse language.
541:
395:SIAM Journal on Computing
369:SIAM Journal on Computing
409:Structural Complexity II
54:with other classes. The
437:Information and Control
174:are sparse, there is a
441:At ACM Digital Library
312:
131:
89:1 bits for some fixed
313:
178:from any language in
132:
415:. pp. 130–131.
278:
102:
266:(as opposed to the
228:set if and only if
34:complexity function
308:
127:
485:. April 18, 2006.
384:25:130–143. 1982.
306:
295:
285:
219:Mahaney's theorem
119:
97:, there are only
532:
520:Formal languages
495:. June 29, 2007.
467:
449:
443:
433:
427:
426:
404:
398:
391:
385:
378:
372:
365:
359:
354:
317:
315:
314:
309:
307:
304:
302:
297:
296:
287:
286:
264:Turing reduction
255:that are not in
136:
134:
133:
128:
126:
125:
124:
111:
56:complexity class
32:) such that the
540:
539:
535:
534:
533:
531:
530:
529:
510:
509:
489:William Gasarch
475:
470:
450:
446:
434:
430:
423:
406:
405:
401:
392:
388:
379:
375:
366:
362:
355:
351:
347:
276:
275:
160:unary languages
158:, the class of
148:
106:
100:
99:
83:unary languages
26:formal language
22:sparse language
12:
11:
5:
538:
536:
528:
527:
522:
512:
511:
508:
507:
500:Complexity Zoo
496:
486:
474:
473:External links
471:
469:
468:
444:
428:
421:
399:
386:
373:
360:
348:
346:
343:
342:
341:
328:problem, then
319:
301:
290:
268:Karp reduction
260:
237:
183:
164:
163:
147:
144:
123:
118:
115:
110:
13:
10:
9:
6:
4:
3:
2:
537:
526:
523:
521:
518:
517:
515:
506:
502:
501:
497:
494:
490:
487:
484:
480:
479:Lance Fortnow
477:
476:
472:
466:
462:
458:
454:
448:
445:
442:
438:
432:
429:
424:
422:3-540-52079-1
418:
414:
410:
403:
400:
396:
390:
387:
383:
377:
374:
370:
364:
361:
358:
353:
350:
344:
339:
338:
333:
332:
327:
325:
320:
299:
288:
273:
269:
265:
261:
258:
254:
250:
249:
244:
243:
238:
235:
231:
227:
225:
220:
216:
212:
208:
206:
201:
200:
196:
191:
189:
184:
181:
177:
173:
171:
166:
165:
161:
157:
153:
150:
149:
145:
143:
141:
137:
116:
113:
96:
92:
88:
84:
80:
76:
72:
68:
63:
61:
57:
53:
52:
47:
43:
39:
35:
31:
27:
23:
19:
498:
452:
447:
436:
431:
408:
402:
394:
389:
381:
376:
368:
363:
352:
335:
329:
323:
271:
256:
252:
246:
240:
233:
229:
223:
214:
210:
204:
198:
194:
187:
179:
169:
155:
151:
139:
94:
90:
86:
78:
74:
70:
66:
64:
59:
49:
45:
44:function of
37:
21:
15:
465:At Citeseer
262:There is a
93:; for each
81:grows. All
514:Categories
345:References
42:polynomial
28:(a set of
461:0022-0000
326:-complete
289:⊆
239:Further,
217:(this is
207:-complete
190:-complete
154:contains
413:Springer
209:, then
192:, then
30:strings
505:SPARSE
459:
419:
152:SPARSE
67:sparse
60:SPARSE
226:-hard
188:co-NP
172:/poly
156:TALLY
24:is a
457:ISSN
417:ISBN
305:poly
20:, a
16:In
516::
503::
491:.
481:.
463:.
411:.
334:=
284:NP
272:NP
253:NP
248:NE
245:â‰
234:NP
232:=
224:NP
215:NP
213:=
205:NP
199:NP
197:=
142:.
62:.
51:NP
425:.
340:.
337:P
331:L
324:P
318:.
300:/
294:P
259:.
257:P
242:E
236:.
230:P
211:P
195:P
180:P
170:P
140:n
122:)
117:k
114:n
109:(
95:n
91:k
87:k
79:n
75:n
71:n
46:n
38:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
