875:
53:
1254:
576:
631:
389:
438:
902:
341:
482:
412:
1259:
462:
895:
518:
115:
888:
252:
167:
1005:
295:
860:
786:
507:
1249:
657:
127:
548:
589:
348:
247:
354:
35:
880:
1274:
1264:
912:
492:
137:
417:
279:
237:
101:
1109:
671:
Solovay, Robert M. (1970). "A model of set-theory in which every set of reals is
Lebesgue measurable".
1227:
1269:
1223:
1183:
1113:
275:
1037:
971:
545:
541:
313:
291:
1033:
987:
724:
688:
583:
488:
79:
1171:
835:
763:
503:
344:
326:
283:
241:
179:
123:
467:
397:
1147:
1057:
1009:
967:
963:
927:
825:
798:
745:
716:
680:
649:
634:
499:
174:
1219:
1157:
1077:
1067:
1027:
1017:
999:
923:
514:
317:
299:
260:
189:
874:
799:"Robert M. Solovay | Department of Mathematics at University of California Berkeley"
197:
736:
Solovay, Robert M. and Volker
Strassen (1977). "A fast Monte-Carlo test for primality".
1205:
1099:
1063:
1051:
977:
949:
931:
633:
as additional axioms) completely axiomatizes the logic of the provability predicate of
522:
447:
441:
256:
201:
193:
31:
1243:
1213:
1201:
1175:
1165:
1141:
1095:
1083:
1073:
1045:
981:
959:
830:
813:
641:
217:
111:
91:
1209:
1161:
1125:
1119:
993:
935:
645:
534:
526:
544:, he proved with T. P. Baker and J. Gill that relativizing arguments cannot prove
1179:
1103:
1089:
1041:
1023:
814:"Relativizations of the P=?NP question over the reals (and other ordered rings)"
530:
287:
157:
1197:
1193:
953:
943:
939:
306:
221:
119:
839:
1187:
1153:
1135:
1131:
52:
856:
782:
491:, developing the method of iterated forcing and showing the consistency of
728:
692:
17:
749:
720:
684:
653:
233:
869:
30:"Solovay" redirects here. For alleged internet "Spam King", see
884:
865:
1255:
Members of the United States
National Academy of Sciences
592:
551:
470:
450:
420:
400:
357:
329:
185:
173:
163:
153:
133:
107:
97:
87:
62:
43:
625:
570:
476:
456:
432:
406:
383:
335:
709:Transactions of the American Mathematical Society
278:showing that, if one assumes the existence of an
57:Robert Solovay in 1993 (photo by George Bergman)
700:Solovay, Robert M. (1967). "A nonconstructible
571:{\displaystyle \mathrm {P} \neq \mathrm {NP} }
896:
8:
626:{\displaystyle \Box (\Box A\to A)\to \Box A}
320:with the existence of a measurable cardinal;
715:(1). American Mathematical Society: 50–75.
913:Paris Kanellakis Theory and Practice Award
903:
889:
881:
873:
40:
829:
648:can efficiently approximate an arbitrary
591:
560:
552:
550:
469:
449:
419:
399:
384:{\displaystyle 2^{\lambda }=\lambda ^{+}}
375:
362:
356:
328:
513:Outside of set theory, developing (with
414:is an uncountable regular cardinal, and
246:A Functorial Form of the Differentiable
216:(born December 15, 1938) is an American
775:
533:. This method has had implications for
586:which has the instances of the schema
251:. Solovay has spent his career at the
7:
1260:20th-century American mathematicians
464:can be decomposed into the union of
253:University of California at Berkeley
255:, where his Ph.D. students include
564:
561:
553:
433:{\displaystyle S\subseteq \kappa }
168:University of California, Berkeley
27:American mathematician (born 1938)
25:
312:Proving that the existence of a
51:
644:, proving that a finite set of
519:Solovay–Strassen primality test
314:real-valued measurable cardinal
240:in 1964 under the direction of
116:Solovay–Strassen primality test
614:
611:
605:
596:
1:
861:Mathematics Genealogy Project
787:Mathematics Genealogy Project
831:10.1016/0304-3975(94)00068-9
818:Theoretical Computer Science
508:cardinality of the continuum
502:, showed the consistency of
282:, then the statement "every
271:Solovay's theorems include:
296:Zermelo–Fraenkel set theory
1291:
812:Emerson, T. (1994-10-10).
29:
919:
738:SIAM Journal on Computing
521:, used to identify large
484:disjoint stationary sets;
349:strongly compact cardinal
244:, with a dissertation on
207:
146:
50:
656:in what is now known as
336:{\displaystyle \lambda }
305:Isolating the notion of
36:Soloway (disambiguation)
506:with arbitrarily large
477:{\displaystyle \kappa }
407:{\displaystyle \kappa }
658:Solovay–Kitaev theorem
627:
572:
478:
458:
434:
408:
385:
337:
138:Paris Kanellakis Award
128:Solovay–Kitaev theorem
34:. For other uses, see
673:Annals of Mathematics
665:Selected publications
628:
582:Proving that GL (the
573:
479:
459:
435:
409:
386:
338:
294:" is consistent with
280:inaccessible cardinal
238:University of Chicago
214:Robert Martin Solovay
102:University of Chicago
872:Bibliography Server
590:
549:
468:
448:
418:
398:
355:
327:
248:Riemann–Roch theorem
542:P versus NP problem
493:Suslin's hypothesis
292:Lebesgue measurable
232:Solovay earned his
1250:American logicians
707:set of integers".
623:
584:normal modal logic
568:
489:Stanley Tennenbaum
474:
454:
430:
404:
381:
343:is a strong limit
333:
80:Brooklyn, New York
1237:
1236:
857:Robert M. Solovay
783:Robert M. Solovay
764:Provability logic
675:. Second Series.
457:{\displaystyle S}
347:, greater than a
345:singular cardinal
276:Solovay's theorem
242:Saunders Mac Lane
211:
210:
186:Doctoral students
180:Saunders Mac Lane
148:Scientific career
73:December 15, 1938
45:Robert M. Solovay
16:(Redirected from
1282:
905:
898:
891:
882:
877:
844:
843:
833:
809:
803:
802:
795:
789:
780:
753:
732:
696:
650:unitary operator
635:Peano arithmetic
632:
630:
629:
624:
577:
575:
574:
569:
567:
556:
500:Donald A. Martin
483:
481:
480:
475:
463:
461:
460:
455:
439:
437:
436:
431:
413:
411:
410:
405:
394:Proving that if
390:
388:
387:
382:
380:
379:
367:
366:
342:
340:
339:
334:
323:Proving that if
175:Doctoral advisor
142:
76:
72:
70:
55:
41:
21:
1290:
1289:
1285:
1284:
1283:
1281:
1280:
1279:
1240:
1239:
1238:
1233:
915:
911:Winners of the
909:
853:
848:
847:
811:
810:
806:
797:
796:
792:
781:
777:
772:
760:
750:10.1137/0206006
735:
721:10.2307/1994631
705:
699:
685:10.2307/1970696
670:
667:
588:
587:
547:
546:
523:natural numbers
515:Volker Strassen
466:
465:
446:
445:
416:
415:
396:
395:
371:
358:
353:
352:
325:
324:
300:axiom of choice
269:
261:Matthew Foreman
230:
200:
196:
192:
190:Matthew Foreman
140:
126:
122:
118:
114:
98:Alma mater
83:
77:
74:
68:
66:
58:
46:
39:
28:
23:
22:
15:
12:
11:
5:
1288:
1286:
1278:
1277:
1272:
1267:
1262:
1257:
1252:
1242:
1241:
1235:
1234:
1232:
1231:
1217:
1191:
1169:
1151:
1145:
1139:
1129:
1123:
1117:
1107:
1093:
1087:
1081:
1071:
1061:
1055:
1049:
1031:
1021:
1003:
997:
991:
985:
975:
957:
947:
920:
917:
916:
910:
908:
907:
900:
893:
885:
879:
878:
866:Robert Solovay
863:
852:
851:External links
849:
846:
845:
804:
790:
774:
773:
771:
768:
767:
766:
759:
756:
755:
754:
733:
703:
697:
666:
663:
662:
661:
638:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
580:
566:
563:
559:
555:
540:Regarding the
538:
511:
504:Martin's axiom
496:
485:
473:
453:
442:stationary set
429:
426:
423:
403:
392:
378:
374:
370:
365:
361:
332:
321:
318:equiconsistent
310:
303:
268:
265:
257:W. Hugh Woodin
229:
226:
209:
208:
205:
204:
202:W. Hugh Woodin
194:Judith Roitman
187:
183:
182:
177:
171:
170:
165:
161:
160:
155:
151:
150:
144:
143:
135:
131:
130:
124:Martin's axiom
109:
108:Known for
105:
104:
99:
95:
94:
89:
85:
84:
78:
64:
60:
59:
56:
48:
47:
44:
32:Robert Soloway
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1287:
1276:
1275:Living people
1273:
1271:
1268:
1266:
1265:Set theorists
1263:
1261:
1258:
1256:
1253:
1251:
1248:
1247:
1245:
1229:
1225:
1221:
1218:
1215:
1211:
1207:
1203:
1199:
1195:
1192:
1189:
1185:
1181:
1177:
1173:
1170:
1167:
1163:
1159:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1111:
1108:
1105:
1101:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1075:
1072:
1069:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1043:
1039:
1035:
1032:
1029:
1025:
1022:
1019:
1015:
1011:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
979:
976:
973:
969:
965:
961:
958:
955:
951:
948:
945:
941:
937:
933:
929:
925:
922:
921:
918:
914:
906:
901:
899:
894:
892:
887:
886:
883:
876:
871:
867:
864:
862:
858:
855:
854:
850:
841:
837:
832:
827:
823:
819:
815:
808:
805:
800:
794:
791:
788:
784:
779:
776:
769:
765:
762:
761:
757:
751:
747:
743:
739:
734:
730:
726:
722:
718:
714:
710:
706:
698:
694:
690:
686:
682:
678:
674:
669:
668:
664:
659:
655:
651:
647:
646:quantum gates
643:
642:Alexei Kitaev
639:
636:
620:
617:
608:
602:
599:
593:
585:
581:
579:
557:
543:
539:
536:
532:
528:
524:
520:
516:
512:
509:
505:
501:
497:
494:
490:
486:
471:
451:
443:
427:
424:
421:
401:
393:
376:
372:
368:
363:
359:
350:
346:
330:
322:
319:
315:
311:
308:
304:
301:
297:
293:
289:
285:
281:
277:
274:
273:
272:
266:
264:
262:
258:
254:
250:
249:
243:
239:
235:
227:
225:
223:
219:
218:mathematician
215:
206:
203:
199:
195:
191:
188:
184:
181:
178:
176:
172:
169:
166:
162:
159:
156:
152:
149:
145:
139:
136:
132:
129:
125:
121:
117:
113:
112:Solovay model
110:
106:
103:
100:
96:
93:
90:
86:
81:
75:(age 85)
65:
61:
54:
49:
42:
37:
33:
19:
1184:Mitzenmacher
1013:
824:(1): 15–22.
821:
817:
807:
793:
778:
744:(1): 84–85.
741:
737:
712:
708:
701:
676:
672:
535:cryptography
298:without the
288:real numbers
270:
245:
231:
213:
212:
198:BetĂĽl Tanbay
164:Institutions
147:
1270:1938 births
679:(1): 1–56.
531:probability
220:working in
158:Mathematics
88:Nationality
1244:Categories
1058:Buchberger
770:References
529:with high
222:set theory
120:Zero sharp
69:1938-12-15
1224:Ferragina
1114:Leiserson
1000:Franaszek
988:Karmarkar
840:0304-3975
618:◻
615:→
606:→
600:◻
594:◻
558:≠
525:that are
472:κ
428:κ
425:⊆
402:κ
373:λ
364:λ
331:λ
236:from the
228:Biography
1206:McSherry
1100:Charikar
1084:Mehlhorn
1034:Holzmann
1028:Schapire
1018:Strassen
972:McMillan
758:See also
92:American
1228:Manzini
1220:Burrows
1166:Szegedy
1158:Gibbons
1148:Pevzner
1142:Shenker
1110:Blumofe
1078:Rogaway
1074:Bellare
1052:Brayton
1038:Kurshan
1014:Solovay
978:Sleator
968:Emerson
932:Hellman
924:Adleman
859:at the
785:at the
729:1994631
693:1970696
652:on one
444:, then
18:Solovay
1230:(2022)
1216:(2021)
1210:Nissim
1190:(2020)
1180:Karlin
1176:Broder
1168:(2019)
1162:Matias
1150:(2018)
1144:(2017)
1138:(2016)
1128:(2015)
1122:(2014)
1120:Demmel
1116:(2013)
1106:(2012)
1096:Broder
1092:(2011)
1086:(2010)
1080:(2009)
1070:(2008)
1068:Vapnik
1064:Cortes
1060:(2007)
1054:(2006)
1048:(2005)
1046:Wolper
1030:(2004)
1024:Freund
1020:(2003)
1006:Miller
1002:(2002)
996:(2001)
990:(2000)
984:(1999)
982:Tarjan
974:(1998)
964:Clarke
960:Bryant
956:(1997)
950:Lempel
946:(1996)
944:Shamir
940:Rivest
936:Merkle
928:Diffie
838:
727:
691:
517:) the
391:holds;
154:Fields
141:(2003)
134:Awards
82:, U.S.
1214:Smith
1202:Dwork
1198:Dinur
1188:Upfal
1104:Indyk
1090:Samet
1042:Vardi
1010:Rabin
994:Myers
725:JSTOR
689:JSTOR
654:qubit
640:With
527:prime
498:With
487:With
440:is a
351:then
234:Ph.D.
1194:Blum
1172:Azar
1154:Alon
1136:Naor
1132:Fiat
1126:Luby
870:DBLP
836:ISSN
267:Work
259:and
63:Born
954:Ziv
868:at
826:doi
822:133
746:doi
717:doi
713:127
681:doi
316:is
290:is
286:of
284:set
1246::
1226:,
1222:,
1212:,
1208:,
1204:,
1200:,
1196:,
1186:,
1182:,
1178:,
1174:,
1164:,
1160:,
1156:,
1134:,
1112:,
1102:,
1098:,
1076:,
1066:,
1044:,
1040:,
1036:,
1026:,
1016:,
1012:,
1008:,
980:,
970:,
966:,
962:,
952:,
942:,
938:,
934:,
930:,
926:,
834:.
820:.
816:.
740:.
723:.
711:.
687:.
677:92
263:.
224:.
71:)
904:e
897:t
890:v
842:.
828::
801:.
752:.
748::
742:6
731:.
719::
704:3
702:Δ
695:.
683::
660:.
637:;
621:A
612:)
609:A
603:A
597:(
578:.
565:P
562:N
554:P
537:;
510:;
495:;
452:S
422:S
377:+
369:=
360:2
309:;
307:0
302:;
67:(
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.