627:, it bets some of its current money that the next bit will be a 0, and the remainder of its money that the next bit will be a 1. It doubles whatever money was placed on the bit that appears next, and it loses the money placed on the bit that did not appear. It must bet all of its money, but it may "bet nothing" by placing half of its money on each bit. For a martingale
751:
martingale that succeeds on the set. We define a set to have p-measure 1 if its complement has p-measure 0. For example, proving the above-mentioned conjecture, that NP does not have p-measure 0, amounts to proving that no polynomial-time martingale succeeds on all of NP.
768:
C if it is in C and "many" other problems in C reduce to it. More specifically, the subset of problems of C which reduce to the problem is a measure one set, in terms of the resource bounded measure. This is a weaker requirement than the problem being
679:. The fact that the martingale is a function that takes as input the string seen so far means that the bets placed are solely a function of the bits already read; no other information may affect the bets (other information being the so-called
211:
that works meaningfully on countable sets of infinite sequences. For this measure to be meaningful, it should reflect something about the underlying definition of each complexity class; namely, that they are defined by
195:) is contained in the language. Thus, sets of real numbers in the unit interval and complexity classes (which are sets of languages) may both be viewed as sets of infinite binary sequences, and thus the techniques of
647:. Although the definition of a martingale has the martingale calculating how much money it will have, rather than calculating what bets to place, because of the constrained nature of the game, knowledge the values
490:
742:
To extend this type of measure to complexity classes, Lutz considered restricting the computational power of the martingale. For instance, if instead of allowing any martingale, we require the martingale to be
369:
733:
573:
288:
430:
105:, in which P is contained. P is known to have p-measure 0, and so the hypothesis "NP does not have p-measure 0" would imply not only that NP and P are unequal, but that NP is, in a
582:
Intuitively, a martingale is a gambler that starts with some finite amount of money (say, one dollar). It reads a sequence of bits indefinitely. After reading the finite prefix
516:
153:
625:
72:
199:
used to measure the size of sets of real numbers may be applied to measure complexity classes. However, since each computable complexity class contains only a
101:" is the statement "NP does not have p-measure 0". Here, p-measure is a generalization of Lebesgue measure to subsets of the complexity class
829:
435:
784:
834:
794:
684:
220:
739:. Thus, we can define a measure 0 set to be one for which there exists a martingale that succeeds on all elements of the set.
300:
693:
533:
230:
176:
93:(the set of all decision problems checkable, but not necessarily solvable, in polynomial time). Since P is a
390:
770:
495:
213:
208:
192:
168:
747:
computable, then we obtain a definition of p-measure: a set of sequences has p-measure 0 if there is a
203:
number of elements(because the number of computable languages is countable), each complexity class has
119:
585:
48:
74:, resource bounded measure gives a method to classify the size of subsets of complexity classes.
790:
800:
765:
204:
82:
35:
31:
744:
376:
207:
0. Thus, to do measure theory inside of complexity classes, we must define an alternative
172:
97:
of NP, this would mean that NP contains more problems than P. A stronger hypothesis than "
90:
86:
43:
17:
196:
106:
102:
78:
823:
164:
814:
690:
The key result relating measure to martingales is Ville's observation that a set
42:. Just as Lebesgue measure gives a method to quantify the size of subsets of the
160:
98:
77:
For instance, computer scientists generally believe that the complexity class
735:
has
Lebesgue measure 0 if and only if there is a martingale that succeeds on
200:
156:
39:
375:(This is Ville's original definition of a martingale, later extended by
485:{\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}
219:
The foundation of resource-bounded measure is Ville's formulation of
94:
184:
786:
696:
588:
536:
498:
438:
393:
303:
233:
122:
51:
167:as an infinite binary sequence, by considering its
727:
619:
567:
510:
484:
424:
363:
282:
216:that can be solved within a given resource bound.
147:
66:
179:) as an infinite binary sequence, by setting the
440:
364:{\displaystyle d(w)={\frac {d(w0)+d(w1)}{2}}}
8:
728:{\displaystyle X\subseteq \{0,1\}^{\infty }}
716:
703:
608:
595:
568:{\displaystyle X\subseteq \{0,1\}^{\infty }}
556:
543:
413:
400:
283:{\displaystyle d:\{0,1\}^{*}\to [0,\infty )}
253:
240:
136:
123:
675:placed on 0 and 1 after seeing the string
719:
695:
611:
587:
559:
535:
497:
443:
437:
416:
392:
319:
302:
256:
232:
139:
121:
58:
54:
53:
50:
187:of the sequence to 1 if and only if the
671:1) suffices to calculate the bets that
89:) is not equal to the complexity class
425:{\displaystyle S\in \{0,1\}^{\infty }}
815:Resource-Bounded Measure Bibliography
7:
575:if it succeeds on every sequence in
720:
560:
511:{\displaystyle S\upharpoonright n}
476:
450:
417:
290:such that, for all finite strings
274:
140:
25:
685:generalized theory of martingales
639:) represents the amount of money
148:{\displaystyle \{0,1\}^{\infty }}
38:. It was originally developed by
620:{\displaystyle w\in \{0,1\}^{*}}
67:{\displaystyle \mathbb {R} ^{n}}
28:Lutz's resource-bounded measure
783:van Melkebeek, Dieter (2001),
502:
470:
464:
458:
447:
352:
343:
334:
325:
313:
307:
277:
265:
262:
1:
643:has after reading the string
109:sense, "much bigger than P".
830:Structural complexity theory
851:
749:polynomial-time computable
835:Measures (measure theory)
157:infinite binary sequences
18:Resource bounded measure
30:is a generalisation of
729:
621:
569:
530:on a set of sequences
512:
486:
426:
365:
284:
214:computational problems
149:
68:
730:
622:
570:
513:
487:
427:
366:
285:
193:lexicographical order
191:th binary string (in
171:. We may also view a
150:
69:
694:
586:
534:
496:
436:
391:
301:
231:
120:
49:
725:
617:
565:
508:
482:
454:
422:
361:
280:
155:is the set of all
145:
64:
36:complexity classes
439:
359:
175:(a set of binary
107:measure-theoretic
83:decision problems
16:(Redirected from
842:
804:
799:, archived from
766:complexity class
734:
732:
731:
726:
724:
723:
626:
624:
623:
618:
616:
615:
574:
572:
571:
566:
564:
563:
517:
515:
514:
509:
491:
489:
488:
483:
453:
431:
429:
428:
423:
421:
420:
379:.) A martingale
370:
368:
367:
362:
360:
355:
320:
289:
287:
286:
281:
261:
260:
205:Lebesgue measure
169:binary expansion
159:. We can view a
154:
152:
151:
146:
144:
143:
81:(the set of all
73:
71:
70:
65:
63:
62:
57:
32:Lebesgue measure
21:
850:
849:
845:
844:
843:
841:
840:
839:
820:
819:
811:
797:
782:
779:
773:for the class.
762:almost complete
758:
756:Almost complete
745:polynomial-time
715:
692:
691:
607:
584:
583:
555:
532:
531:
526:. A martingale
494:
493:
434:
433:
412:
389:
388:
377:Joseph Leo Doob
321:
299:
298:
252:
229:
228:
135:
118:
117:
115:
87:polynomial time
52:
47:
46:
44:Euclidean space
23:
22:
15:
12:
11:
5:
848:
846:
838:
837:
832:
822:
821:
818:
817:
810:
809:External links
807:
806:
805:
795:
778:
775:
757:
754:
722:
718:
714:
711:
708:
705:
702:
699:
614:
610:
606:
603:
600:
597:
594:
591:
562:
558:
554:
551:
548:
545:
542:
539:
507:
504:
501:
481:
478:
475:
472:
469:
466:
463:
460:
457:
452:
449:
446:
442:
441:lim sup
419:
415:
411:
408:
405:
402:
399:
396:
387:on a sequence
373:
372:
358:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
318:
315:
312:
309:
306:
279:
276:
273:
270:
267:
264:
259:
255:
251:
248:
245:
242:
239:
236:
227:is a function
197:measure theory
142:
138:
134:
131:
128:
125:
114:
111:
61:
56:
24:
14:
13:
10:
9:
6:
4:
3:
2:
847:
836:
833:
831:
828:
827:
825:
816:
813:
812:
808:
803:on 2011-07-19
802:
798:
796:3-540-41492-4
792:
788:
787:
781:
780:
776:
774:
772:
767:
763:
760:A problem is
755:
753:
750:
746:
740:
738:
712:
709:
706:
700:
697:
688:
686:
682:
678:
674:
670:
666:
662:
658:
654:
650:
646:
642:
638:
634:
630:
612:
604:
601:
598:
592:
589:
580:
578:
552:
549:
546:
540:
537:
529:
525:
521:
518:is the first
505:
499:
479:
473:
467:
461:
455:
444:
409:
406:
403:
397:
394:
386:
382:
378:
356:
349:
346:
340:
337:
331:
328:
322:
316:
310:
304:
297:
296:
295:
293:
271:
268:
257:
249:
246:
243:
237:
234:
226:
222:
217:
215:
210:
206:
202:
198:
194:
190:
186:
182:
178:
174:
170:
166:
165:unit interval
162:
158:
132:
129:
126:
112:
110:
108:
104:
100:
96:
92:
88:
84:
80:
75:
59:
45:
41:
37:
33:
29:
19:
801:the original
789:, Springer,
785:
761:
759:
748:
741:
736:
689:
680:
676:
672:
668:
664:
660:
656:
652:
648:
644:
640:
636:
632:
628:
581:
576:
527:
523:
519:
384:
380:
374:
291:
224:
218:
188:
180:
116:
85:solvable in
76:
27:
26:
383:is said to
221:martingales
161:real number
99:P is not NP
824:Categories
777:References
681:filtration
225:martingale
113:Definition
721:∞
701:⊆
613:∗
593:∈
561:∞
541:⊆
503:↾
477:∞
465:↾
451:∞
448:→
418:∞
398:∈
275:∞
263:→
258:∗
201:countable
141:∞
40:Jack Lutz
771:complete
663:0), and
528:succeeds
522:bits of
173:language
683:in the
385:succeed
209:measure
177:strings
163:in the
793:
764:for a
492:where
95:subset
791:ISBN
223:. A
687:).
655:),
579:.
432:if
185:bit
183:th
34:to
826::
631:,
294:,
91:NP
737:X
717:}
713:1
710:,
707:0
704:{
698:X
677:w
673:d
669:w
667:(
665:d
661:w
659:(
657:d
653:w
651:(
649:d
645:w
641:d
637:w
635:(
633:d
629:d
609:}
605:1
602:,
599:0
596:{
590:w
577:X
557:}
553:1
550:,
547:0
544:{
538:X
524:S
520:n
506:n
500:S
480:,
474:=
471:)
468:n
462:S
459:(
456:d
445:n
414:}
410:1
407:,
404:0
401:{
395:S
381:d
371:.
357:2
353:)
350:1
347:w
344:(
341:d
338:+
335:)
332:0
329:w
326:(
323:d
317:=
314:)
311:w
308:(
305:d
292:w
278:)
272:,
269:0
266:[
254:}
250:1
247:,
244:0
241:{
238::
235:d
189:n
181:n
137:}
133:1
130:,
127:0
124:{
103:E
79:P
60:n
55:R
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.