24:
is a transformation from one computational problem to another, used to relate the difficulty of improving the time bounds for the two problems. Intuitively, it provides a method for solving one problem efficiently by using the solution to the other problem as a
780:
1040:
1145:
646:
1461:
The term "fine-grained reduction" comes from later work by
Virginia Vassilevska Williams in an invited presentation at the 10th International Symposium on Parameterized and Exact Computation.
1587:; Mihajlin, Ivan; Paturi, Ramamohan; Schneider, Stefan (2016), "Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility",
961:
521:
1440:
1066:
547:
835:
1165:
855:
1569:. A preliminary version of these results, including the definition of a "subcubic reduction", a special case of a fine-grained reduction, was presented at the 2010
1197:
915:
815:
693:
475:
420:
157:
1338:
1289:
125:
76:
1386:
1366:
1309:
1260:
1237:
1217:
1086:
981:
935:
883:
666:
587:
567:
495:
443:
389:
369:
349:
325:
305:
285:
265:
237:
217:
197:
177:
96:
47:
1570:
698:
1450:
between two given vertices in a weighted graph, finding negative-weight triangles in weighted graphs, and testing whether a given
1458:. According to their results, either all of these problems have time bounds with exponents less than three, or none of them do.
1464:
Although the original definition of fine-grained reductions involved deterministic algorithms, the corresponding concepts for
1503:(2015), "Hardness of easy problems: basing hardness on popular conjectures such as the Strong Exponential Time Hypothesis",
986:
1091:
592:
1529:
1393:
1507:, LIPIcs. Leibniz Int. Proc. Inform., vol. 43, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 17–29,
1615:
17:
1525:
1500:
1389:
1469:
940:
500:
1399:
1045:
526:
1447:
820:
328:
1589:
ITCS'16—Proceedings of the 2016 ACM Conference on
Innovations in Theoretical Computer Science
1443:
1150:
840:
1596:
1565:
1512:
1465:
1170:
888:
788:
671:
448:
398:
391:
are the time bounds for known or naive algorithms for the two problems, and often they are
130:
1314:
1265:
101:
52:
8:
1584:
287:
be computational problems, specified as the desired output for each possible input. Let
1534:
1371:
1351:
1294:
1245:
1222:
1202:
1071:
966:
920:
868:
651:
572:
552:
480:
428:
374:
354:
334:
310:
290:
270:
250:
222:
202:
182:
162:
81:
32:
1551:
1543:
1592:
1561:
1508:
1451:
1219:
by applying the transformation of the reduction and using the fast algorithm for
1609:
1532:(2018), "Subcubic equivalences between path, matrix, and triangle problems",
1455:
1556:
26:
1547:
1505:
10th
International Symposium on Parameterized and Exact Computation
775:{\displaystyle \sum _{i}b(n_{i})^{1-\epsilon }<a(n)^{1-\delta }}
392:
1582:
1348:
Fine-grained reductions were defined, in the special case that
569:
by transforming it into a sequence of instances of problem
1402:
1374:
1354:
1317:
1297:
1268:
1248:
1225:
1205:
1173:
1153:
1094:
1074:
1048:
1035:{\displaystyle O{\bigl (}b(n)^{1-\epsilon }{\bigr )}}
989:
969:
943:
923:
891:
871:
843:
823:
791:
701:
674:
654:
595:
575:
555:
529:
503:
483:
451:
431:
401:
377:
357:
337:
313:
293:
273:
253:
225:
205:
185:
165:
133:
104:
84:
55:
35:
668:, and producing a sequence of instances whose sizes
1311:cannot be solved in time significantly faster than
1262:cannot be solved in time significantly faster than
1140:{\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}
641:{\displaystyle O{\bigl (}a(n)^{1-\delta }{\bigr )}}
1434:
1380:
1360:
1332:
1303:
1283:
1254:
1231:
1211:
1191:
1159:
1139:
1080:
1060:
1042:. Then, with these assumptions, there also exists
1034:
975:
955:
929:
909:
877:
849:
829:
809:
774:
687:
660:
640:
581:
561:
549:and an algorithm that solves instances of problem
541:
515:
489:
469:
437:
414:
383:
363:
343:
319:
299:
279:
259:
231:
211:
191:
171:
151:
119:
90:
70:
41:
199:implies that any significant speedup for problem
1607:
1524:
1442:-reductions between several problems including
1132:
1100:
1027:
995:
633:
601:
1571:Symposium on Foundations of Computer Science
648:for the transformation on instances of size
1396:in 2010. They also showed the existence of
1555:
219:would also lead to a speedup for problem
1499:
817:-reduction is given by the mapping from
351:and produce an integer result. Usually,
1608:
860:
1576:
1495:
1493:
1491:
1489:
1487:
1485:
1591:, ACM, New York, pp. 261–270,
1518:
13:
1583:Carmosino, Marco L.; Gao, Jiawei;
1482:
14:
1627:
837:to the pair of an algorithm and
1239:for each resulting subproblem.
18:computational complexity theory
1526:Williams, Virginia Vassilevska
1429:
1403:
1327:
1321:
1278:
1272:
1186:
1174:
1115:
1108:
1010:
1003:
956:{\displaystyle \epsilon >0}
904:
892:
804:
792:
757:
750:
729:
715:
616:
609:
516:{\displaystyle \epsilon >0}
464:
452:
331:that take an integer argument
146:
134:
114:
108:
65:
59:
1:
1475:
1435:{\displaystyle (n^{3},n^{3})}
1390:Virginia Vassilevska Williams
523:, there exists a real number
242:
1061:{\displaystyle \delta >0}
542:{\displaystyle \delta >0}
329:time-constructible functions
7:
1472:have also been considered.
1470:nondeterministic algorithms
127:, then the existence of an
10:
1632:
1343:
1167:be the value given by the
497:if, for every real number
830:{\displaystyle \epsilon }
1444:all-pairs shortest paths
1388:are equal monomials, by
159:-reduction from problem
1160:{\displaystyle \delta }
850:{\displaystyle \delta }
1616:Reduction (complexity)
1436:
1382:
1362:
1334:
1305:
1285:
1256:
1233:
1213:
1199:-reduction, and solve
1193:
1161:
1141:
1088:can be solved in time
1082:
1062:
1036:
983:can be solved in time
977:
957:
931:
911:
879:
851:
831:
811:
776:
689:
662:
642:
583:
563:
543:
517:
491:
471:
439:
416:
385:
365:
345:
321:
301:
281:
261:
233:
213:
193:
173:
153:
121:
98:can be solved in time
92:
72:
49:can be solved in time
43:
22:fine-grained reduction
1501:Williams, Virginia V.
1466:randomized algorithms
1437:
1383:
1363:
1335:
1306:
1286:
1257:
1234:
1214:
1194:
1192:{\displaystyle (a,b)}
1162:
1142:
1083:
1063:
1037:
978:
958:
932:
912:
910:{\displaystyle (a,b)}
880:
852:
832:
812:
810:{\displaystyle (a,b)}
777:
690:
688:{\displaystyle n_{i}}
663:
643:
584:
564:
544:
518:
492:
472:
470:{\displaystyle (a,b)}
440:
417:
415:{\displaystyle n^{2}}
386:
366:
346:
322:
302:
282:
262:
234:
214:
194:
174:
154:
152:{\displaystyle (a,b)}
122:
93:
73:
44:
1585:Impagliazzo, Russell
1448:second-shortest path
1400:
1372:
1352:
1333:{\displaystyle b(n)}
1315:
1295:
1284:{\displaystyle a(n)}
1266:
1246:
1223:
1203:
1171:
1151:
1092:
1072:
1046:
987:
967:
941:
921:
889:
869:
841:
821:
789:
699:
672:
652:
593:
573:
553:
527:
501:
481:
449:
429:
399:
375:
355:
335:
311:
291:
271:
251:
223:
203:
183:
163:
131:
120:{\displaystyle b(n)}
102:
82:
71:{\displaystyle a(n)}
53:
33:
1542:(5): A27:1–A27:38,
937:, and there exists
861:Speedup implication
1535:Journal of the ACM
1432:
1378:
1358:
1330:
1301:
1281:
1252:
1229:
1209:
1189:
1157:
1137:
1078:
1058:
1032:
973:
953:
927:
907:
875:
847:
827:
807:
772:
711:
685:
658:
638:
579:
559:
539:
513:
487:
467:
435:
412:
381:
361:
341:
317:
297:
277:
257:
229:
209:
189:
169:
149:
117:
88:
68:
39:
1530:Williams, R. Ryan
1381:{\displaystyle b}
1361:{\displaystyle a}
1304:{\displaystyle B}
1255:{\displaystyle A}
1242:Equivalently, if
1232:{\displaystyle B}
1212:{\displaystyle A}
1081:{\displaystyle A}
976:{\displaystyle B}
930:{\displaystyle B}
878:{\displaystyle A}
702:
661:{\displaystyle n}
582:{\displaystyle B}
562:{\displaystyle A}
490:{\displaystyle B}
438:{\displaystyle A}
384:{\displaystyle b}
364:{\displaystyle a}
344:{\displaystyle n}
320:{\displaystyle b}
300:{\displaystyle a}
280:{\displaystyle B}
260:{\displaystyle A}
232:{\displaystyle A}
212:{\displaystyle B}
192:{\displaystyle B}
172:{\displaystyle A}
91:{\displaystyle B}
42:{\displaystyle A}
1623:
1600:
1599:
1580:
1574:
1568:
1559:
1522:
1516:
1515:
1497:
1441:
1439:
1438:
1433:
1428:
1427:
1415:
1414:
1387:
1385:
1384:
1379:
1367:
1365:
1364:
1359:
1339:
1337:
1336:
1331:
1310:
1308:
1307:
1302:
1290:
1288:
1287:
1282:
1261:
1259:
1258:
1253:
1238:
1236:
1235:
1230:
1218:
1216:
1215:
1210:
1198:
1196:
1195:
1190:
1166:
1164:
1163:
1158:
1146:
1144:
1143:
1138:
1136:
1135:
1129:
1128:
1104:
1103:
1087:
1085:
1084:
1079:
1067:
1065:
1064:
1059:
1041:
1039:
1038:
1033:
1031:
1030:
1024:
1023:
999:
998:
982:
980:
979:
974:
962:
960:
959:
954:
936:
934:
933:
928:
916:
914:
913:
908:
884:
882:
881:
876:
856:
854:
853:
848:
836:
834:
833:
828:
816:
814:
813:
808:
781:
779:
778:
773:
771:
770:
743:
742:
727:
726:
710:
694:
692:
691:
686:
684:
683:
667:
665:
664:
659:
647:
645:
644:
639:
637:
636:
630:
629:
605:
604:
588:
586:
585:
580:
568:
566:
565:
560:
548:
546:
545:
540:
522:
520:
519:
514:
496:
494:
493:
488:
476:
474:
473:
468:
444:
442:
441:
436:
421:
419:
418:
413:
411:
410:
390:
388:
387:
382:
370:
368:
367:
362:
350:
348:
347:
342:
326:
324:
323:
318:
306:
304:
303:
298:
286:
284:
283:
278:
266:
264:
263:
258:
238:
236:
235:
230:
218:
216:
215:
210:
198:
196:
195:
190:
178:
176:
175:
170:
158:
156:
155:
150:
126:
124:
123:
118:
97:
95:
94:
89:
77:
75:
74:
69:
48:
46:
45:
40:
1631:
1630:
1626:
1625:
1624:
1622:
1621:
1620:
1606:
1605:
1604:
1603:
1581:
1577:
1548:10.1145/3186893
1523:
1519:
1498:
1483:
1478:
1452:distance matrix
1423:
1419:
1410:
1406:
1401:
1398:
1397:
1373:
1370:
1369:
1353:
1350:
1349:
1346:
1316:
1313:
1312:
1296:
1293:
1292:
1267:
1264:
1263:
1247:
1244:
1243:
1224:
1221:
1220:
1204:
1201:
1200:
1172:
1169:
1168:
1152:
1149:
1148:
1131:
1130:
1118:
1114:
1099:
1098:
1093:
1090:
1089:
1073:
1070:
1069:
1047:
1044:
1043:
1026:
1025:
1013:
1009:
994:
993:
988:
985:
984:
968:
965:
964:
942:
939:
938:
922:
919:
918:
890:
887:
886:
870:
867:
866:
863:
842:
839:
838:
822:
819:
818:
790:
787:
786:
760:
756:
732:
728:
722:
718:
706:
700:
697:
696:
695:are bounded by
679:
675:
673:
670:
669:
653:
650:
649:
632:
631:
619:
615:
600:
599:
594:
591:
590:
574:
571:
570:
554:
551:
550:
528:
525:
524:
502:
499:
498:
482:
479:
478:
450:
447:
446:
430:
427:
426:
406:
402:
400:
397:
396:
376:
373:
372:
356:
353:
352:
336:
333:
332:
312:
309:
308:
292:
289:
288:
272:
269:
268:
252:
249:
248:
245:
224:
221:
220:
204:
201:
200:
184:
181:
180:
164:
161:
160:
132:
129:
128:
103:
100:
99:
83:
80:
79:
54:
51:
50:
34:
31:
30:
12:
11:
5:
1629:
1619:
1618:
1602:
1601:
1575:
1517:
1480:
1479:
1477:
1474:
1446:, finding the
1431:
1426:
1422:
1418:
1413:
1409:
1405:
1377:
1357:
1345:
1342:
1329:
1326:
1323:
1320:
1300:
1280:
1277:
1274:
1271:
1251:
1228:
1208:
1188:
1185:
1182:
1179:
1176:
1156:
1147:. Namely, let
1134:
1127:
1124:
1121:
1117:
1113:
1110:
1107:
1102:
1097:
1077:
1057:
1054:
1051:
1029:
1022:
1019:
1016:
1012:
1008:
1005:
1002:
997:
992:
972:
952:
949:
946:
926:
917:-reducible to
906:
903:
900:
897:
894:
874:
862:
859:
846:
826:
806:
803:
800:
797:
794:
769:
766:
763:
759:
755:
752:
749:
746:
741:
738:
735:
731:
725:
721:
717:
714:
709:
705:
682:
678:
657:
635:
628:
625:
622:
618:
614:
611:
608:
603:
598:
589:, taking time
578:
558:
538:
535:
532:
512:
509:
506:
486:
477:-reducible to
466:
463:
460:
457:
454:
445:is said to be
434:
409:
405:
380:
360:
340:
316:
296:
276:
256:
244:
241:
228:
208:
188:
168:
148:
145:
142:
139:
136:
116:
113:
110:
107:
87:
67:
64:
61:
58:
38:
9:
6:
4:
3:
2:
1628:
1617:
1614:
1613:
1611:
1598:
1594:
1590:
1586:
1579:
1572:
1567:
1563:
1558:
1557:1721.1/134750
1553:
1549:
1545:
1541:
1537:
1536:
1531:
1527:
1521:
1514:
1510:
1506:
1502:
1496:
1494:
1492:
1490:
1488:
1486:
1481:
1473:
1471:
1467:
1462:
1459:
1457:
1453:
1449:
1445:
1424:
1420:
1416:
1411:
1407:
1395:
1394:Ryan Williams
1391:
1375:
1355:
1341:
1324:
1318:
1298:
1275:
1269:
1249:
1240:
1226:
1206:
1183:
1180:
1177:
1154:
1125:
1122:
1119:
1111:
1105:
1095:
1075:
1055:
1052:
1049:
1020:
1017:
1014:
1006:
1000:
990:
970:
950:
947:
944:
924:
901:
898:
895:
872:
858:
844:
824:
801:
798:
795:
783:
767:
764:
761:
753:
747:
744:
739:
736:
733:
723:
719:
712:
707:
703:
680:
676:
655:
626:
623:
620:
612:
606:
596:
576:
556:
536:
533:
530:
510:
507:
504:
484:
461:
458:
455:
432:
423:
407:
403:
394:
378:
358:
338:
330:
314:
294:
274:
254:
240:
226:
206:
186:
166:
143:
140:
137:
111:
105:
85:
62:
56:
36:
29:. If problem
28:
23:
19:
1588:
1578:
1539:
1533:
1520:
1504:
1463:
1460:
1456:metric space
1454:describes a
1347:
1241:
864:
784:
424:
246:
78:and problem
21:
15:
179:to problem
1476:References
1068:such that
963:such that
243:Definition
27:subroutine
1155:δ
1126:δ
1123:−
1050:δ
1021:ϵ
1018:−
945:ϵ
845:δ
825:ϵ
768:δ
765:−
740:ϵ
737:−
704:∑
627:δ
624:−
531:δ
505:ϵ
393:monomials
1610:Category
865:Suppose
395:such as
327:both be
1597:3629829
1566:3856539
1513:3452406
1344:History
1291:, then
1595:
1564:
1511:
425:Then
1468:and
1392:and
1368:and
1053:>
948:>
745:<
534:>
508:>
371:and
307:and
267:and
247:Let
20:, a
1552:hdl
1544:doi
885:is
785:An
16:In
1612::
1593:MR
1562:MR
1560:,
1550:,
1540:65
1538:,
1528:;
1509:MR
1484:^
1340:.
857:.
782:.
422:.
239:.
1573:.
1554::
1546::
1430:)
1425:3
1421:n
1417:,
1412:3
1408:n
1404:(
1376:b
1356:a
1328:)
1325:n
1322:(
1319:b
1299:B
1279:)
1276:n
1273:(
1270:a
1250:A
1227:B
1207:A
1187:)
1184:b
1181:,
1178:a
1175:(
1133:)
1120:1
1116:)
1112:n
1109:(
1106:a
1101:(
1096:O
1076:A
1056:0
1028:)
1015:1
1011:)
1007:n
1004:(
1001:b
996:(
991:O
971:B
951:0
925:B
905:)
902:b
899:,
896:a
893:(
873:A
805:)
802:b
799:,
796:a
793:(
762:1
758:)
754:n
751:(
748:a
734:1
730:)
724:i
720:n
716:(
713:b
708:i
681:i
677:n
656:n
634:)
621:1
617:)
613:n
610:(
607:a
602:(
597:O
577:B
557:A
537:0
511:0
485:B
465:)
462:b
459:,
456:a
453:(
433:A
408:2
404:n
379:b
359:a
339:n
315:b
295:a
275:B
255:A
227:A
207:B
187:B
167:A
147:)
144:b
141:,
138:a
135:(
115:)
112:n
109:(
106:b
86:B
66:)
63:n
60:(
57:a
37:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.