742:
383:
737:{\displaystyle \exists S_{1}\exists S_{2}\exists S_{3}\,\forall u\forall v\,{\bigl (}S_{1}(u)\vee S_{2}(u)\vee S_{3}(u){\bigr )}\,\wedge \,{\bigl (}E(u,v)\,\implies \,(\neg S_{1}(u)\vee \neg S_{1}(v))\,\wedge \,\left(\neg S_{2}(u)\vee \neg S_{2}(v)\right)\,\wedge \,(\neg S_{3}(u)\vee \neg S_{3}(v)){\bigr )}}
248:
1073:
365:
is a quantifier-free formula: any boolean combination of the relations. That is, only existential second-order quantification (over relations) is allowed and only universal first-order quantification (over vertices) is allowed. If existential quantification over vertices were also allowed, the
74:
869:
343:
297:
818:
363:
765:
243:{\displaystyle \exists S_{1}\dots \exists S_{\ell }\,\forall v_{1}\dots \forall v_{m}\,\phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})}
1068:{\displaystyle \max \limits _{S_{1},\dots ,S_{\ell }}|\{(v_{1},\dots ,v_{m})\colon \phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})\}|}
366:
resulting complexity class would be equal to NP (more precisely, the class of those properties of relational structures that are in NP), a fact known as
1177:
1349:
1119:
and at most 3 literals per clause), find an assignment satisfying as many clauses as possible. In fact, it is a natural
1268:
20:
1282:
Papadimitriou, Christos H.; Yannakakis, Mihalis (1991). "Optimization, approximation, and complexity classes".
1244:
1112:
825:
863:
is defined as the class of optimization problems on relational structures expressible in the following form:
302:
61:
1419:
256:
770:
1131:
1116:
829:
1341:
1148:, the class of all problems approximable to within some constant ratio. In fact the closure of
374:
1120:
820:
correspond to sets of vertices colored with one of the 3 colors. Similarly, SNP contains the
1329:
849:
348:
57:
50:
1359:
1303:
1225:
Feder, Tomás; Vardi, Moshe Y. (1993). "Monotone monadic SNP and constraint satisfaction".
373:
For example, SNP contains 3-Coloring (the problem of determining whether a given graph is
8:
1262:
1250:
856:
tuples, one wants to maximize the number of tuples for which it is satisfied. That is,
750:
367:
65:
1227:
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93
1401:
1345:
1330:
1295:
1240:
1390:
767:
denotes the adjacency relation of the input graph, while the sets (unary relations)
1355:
1299:
1291:
1254:
1230:
32:
1379:
1337:
37:
1396:
1385:
1374:
1325:
1165:
1153:
299:
are relations of the structure (such as the adjacency relation, for a graph),
1413:
1317:
1321:
42:
1235:
1184:-complete (under PTAS reductions), and hence does not admit a PTAS unless
1189:
1082:
1101:
1336:. Texts in Theoretical Computer Science. An EATCS Series. Berlin:
46:
45:
properties. It forms the basis for the definition of the class
56:
It is defined as the class of problems that are properties of
1315:
377:), because it can be expressed by the following formula:
1205:
1144:
345:
are unknown relations (sets of tuples of vertices), and
1281:
852:, when instead of asking a formula to be satisfied for
1156:(slightly more general than L-reductions) is equal to
1081:
is then defined as the class of all problems with an
872:
773:
753:
386:
351:
305:
259:
77:
1067:
812:
759:
736:
357:
337:
291:
242:
41:based on its logical characterization in terms of
1411:
1176:-complete problem (under L-reductions or under
729:
524:
512:
442:
1188:. However, the proof of this relies on the
1057:
914:
1224:
552:
548:
1234:
828:(SAT) where the formula is restricted to
673:
669:
611:
607:
553:
547:
521:
517:
439:
426:
137:
107:
1332:Finite model theory and its applications
1328:; Venema, Yde; Weinstein, Scott (2007).
1412:
1111:: given an instance of 3-CNF-SAT (the
338:{\displaystyle S_{1},\dots ,S_{\ell }}
1316:Grädel, Erich; Kolaitis, Phokion G.;
1196:-completeness are often elementary.
13:
848:An analogous definition considers
702:
677:
642:
617:
582:
557:
433:
427:
413:
400:
387:
292:{\displaystyle R_{1},\dots ,R_{k}}
124:
108:
94:
78:
14:
1431:
1367:
813:{\displaystyle S_{1},S_{2},S_{3}}
68:formula of the following form:
35:containing a limited subset of
21:computational complexity theory
1275:
1218:
1113:boolean satisfiability problem
1061:
1054:
958:
949:
917:
910:
826:boolean satisfiability problem
724:
721:
715:
696:
690:
674:
661:
655:
636:
630:
604:
601:
595:
576:
570:
554:
549:
544:
532:
507:
501:
485:
479:
463:
457:
237:
141:
1:
1267:: CS1 maint: date and year (
1211:
1296:10.1016/0022-0000(91)90023-X
1160:; that is, every problem in
7:
1199:
1168:to it from some problem in
874:
836:literals per clause, where
10:
1436:
843:
1134:to solve any problem in
1172:. In particular, every
1132:approximation algorithm
1130:There is a fixed-ratio
1117:conjunctive normal form
830:conjunctive normal form
1069:
814:
761:
738:
359:
339:
293:
244:
1236:10.1145/167088.167245
1070:
850:optimization problems
815:
762:
739:
360:
358:{\displaystyle \phi }
340:
294:
245:
58:relational structures
51:optimization problems
1284:J. Comput. Syst. Sci
1229:. pp. 612–622.
1115:with the formula in
870:
771:
751:
384:
349:
303:
257:
75:
1091:log-space reduction
64:) expressible by a
1420:Complexity classes
1192:, while proofs of
1065:
908:
824:-SAT problem: the
810:
757:
734:
355:
335:
289:
240:
66:second-order logic
1351:978-3-540-00428-8
1320:; Maarten, Marx;
1093:) to problems in
873:
760:{\displaystyle E}
43:graph-theoretical
1427:
1363:
1335:
1308:
1307:
1279:
1273:
1272:
1266:
1258:
1238:
1222:
1142:is contained in
1104:is a problem in
1087:linear reduction
1074:
1072:
1071:
1066:
1064:
1053:
1052:
1034:
1033:
1021:
1020:
1002:
1001:
989:
988:
970:
969:
948:
947:
929:
928:
913:
907:
906:
905:
887:
886:
819:
817:
816:
811:
809:
808:
796:
795:
783:
782:
766:
764:
763:
758:
743:
741:
740:
735:
733:
732:
714:
713:
689:
688:
668:
664:
654:
653:
629:
628:
594:
593:
569:
568:
528:
527:
516:
515:
500:
499:
478:
477:
456:
455:
446:
445:
425:
424:
412:
411:
399:
398:
364:
362:
361:
356:
344:
342:
341:
336:
334:
333:
315:
314:
298:
296:
295:
290:
288:
287:
269:
268:
249:
247:
246:
241:
236:
235:
217:
216:
204:
203:
185:
184:
172:
171:
153:
152:
136:
135:
120:
119:
106:
105:
90:
89:
33:complexity class
16:Complexity class
1435:
1434:
1430:
1429:
1428:
1426:
1425:
1424:
1410:
1409:
1405:
1370:
1352:
1338:Springer-Verlag
1326:Vardi, Moshe Y.
1312:
1311:
1280:
1276:
1260:
1259:
1247:
1223:
1219:
1214:
1202:
1154:PTAS reductions
1109:
1100:. For example,
1098:
1060:
1048:
1044:
1029:
1025:
1016:
1012:
997:
993:
984:
980:
965:
961:
943:
939:
924:
920:
909:
901:
897:
882:
878:
877:
871:
868:
867:
861:
846:
832:and to at most
804:
800:
791:
787:
778:
774:
772:
769:
768:
752:
749:
748:
728:
727:
709:
705:
684:
680:
649:
645:
624:
620:
616:
612:
589:
585:
564:
560:
523:
522:
511:
510:
495:
491:
473:
469:
451:
447:
441:
440:
420:
416:
407:
403:
394:
390:
385:
382:
381:
368:Fagin's theorem
350:
347:
346:
329:
325:
310:
306:
304:
301:
300:
283:
279:
264:
260:
258:
255:
254:
231:
227:
212:
208:
199:
195:
180:
176:
167:
163:
148:
144:
131:
127:
115:
111:
101:
97:
85:
81:
76:
73:
72:
17:
12:
11:
5:
1433:
1423:
1422:
1408:
1407:
1403:
1397:Complexity Zoo
1393:
1386:Complexity Zoo
1382:
1375:Complexity Zoo
1369:
1368:External links
1366:
1365:
1364:
1350:
1318:Libkin, Leonid
1310:
1309:
1290:(3): 425–440.
1274:
1245:
1216:
1215:
1213:
1210:
1209:
1208:
1201:
1198:
1166:PTAS reduction
1107:
1096:
1076:
1075:
1063:
1059:
1056:
1051:
1047:
1043:
1040:
1037:
1032:
1028:
1024:
1019:
1015:
1011:
1008:
1005:
1000:
996:
992:
987:
983:
979:
976:
973:
968:
964:
960:
957:
954:
951:
946:
942:
938:
935:
932:
927:
923:
919:
916:
912:
904:
900:
896:
893:
890:
885:
881:
876:
859:
845:
842:
807:
803:
799:
794:
790:
786:
781:
777:
756:
745:
744:
731:
726:
723:
720:
717:
712:
708:
704:
701:
698:
695:
692:
687:
683:
679:
676:
672:
667:
663:
660:
657:
652:
648:
644:
641:
638:
635:
632:
627:
623:
619:
615:
610:
606:
603:
600:
597:
592:
588:
584:
581:
578:
575:
572:
567:
563:
559:
556:
551:
546:
543:
540:
537:
534:
531:
526:
520:
514:
509:
506:
503:
498:
494:
490:
487:
484:
481:
476:
472:
468:
465:
462:
459:
454:
450:
444:
438:
435:
432:
429:
423:
419:
415:
410:
406:
402:
397:
393:
389:
354:
332:
328:
324:
321:
318:
313:
309:
286:
282:
278:
275:
272:
267:
263:
251:
250:
239:
234:
230:
226:
223:
220:
215:
211:
207:
202:
198:
194:
191:
188:
183:
179:
175:
170:
166:
162:
159:
156:
151:
147:
143:
140:
134:
130:
126:
123:
118:
114:
110:
104:
100:
96:
93:
88:
84:
80:
15:
9:
6:
4:
3:
2:
1432:
1421:
1418:
1417:
1415:
1406:
1399:
1398:
1394:
1392:
1388:
1387:
1383:
1381:
1377:
1376:
1372:
1371:
1361:
1357:
1353:
1347:
1343:
1339:
1334:
1333:
1327:
1323:
1322:Spencer, Joel
1319:
1314:
1313:
1305:
1301:
1297:
1293:
1289:
1285:
1278:
1270:
1264:
1256:
1252:
1248:
1242:
1237:
1232:
1228:
1221:
1217:
1207:
1204:
1203:
1197:
1195:
1191:
1187:
1183:
1179:
1178:AP-reductions
1175:
1171:
1167:
1163:
1159:
1155:
1151:
1147:
1146:
1141:
1137:
1133:
1128:
1126:
1122:
1118:
1114:
1110:
1103:
1099:
1092:
1088:
1084:
1080:
1049:
1045:
1041:
1038:
1035:
1030:
1026:
1022:
1017:
1013:
1009:
1006:
1003:
998:
994:
990:
985:
981:
977:
974:
971:
966:
962:
955:
952:
944:
940:
936:
933:
930:
925:
921:
902:
898:
894:
891:
888:
883:
879:
866:
865:
864:
862:
855:
851:
841:
839:
835:
831:
827:
823:
805:
801:
797:
792:
788:
784:
779:
775:
754:
718:
710:
706:
699:
693:
685:
681:
670:
665:
658:
650:
646:
639:
633:
625:
621:
613:
608:
598:
590:
586:
579:
573:
565:
561:
541:
538:
535:
529:
518:
504:
496:
492:
488:
482:
474:
470:
466:
460:
452:
448:
436:
430:
421:
417:
408:
404:
395:
391:
380:
379:
378:
376:
371:
369:
352:
330:
326:
322:
319:
316:
311:
307:
284:
280:
276:
273:
270:
265:
261:
232:
228:
224:
221:
218:
213:
209:
205:
200:
196:
192:
189:
186:
181:
177:
173:
168:
164:
160:
157:
154:
149:
145:
138:
132:
128:
121:
116:
112:
102:
98:
91:
86:
82:
71:
70:
69:
67:
63:
59:
54:
52:
48:
44:
40:
39:
34:
30:
26:
22:
1395:
1384:
1373:
1331:
1287:
1283:
1277:
1226:
1220:
1193:
1185:
1181:
1173:
1169:
1161:
1157:
1149:
1143:
1139:
1135:
1129:
1124:
1123:problem for
1105:
1094:
1090:
1086:
1078:
1077:
857:
853:
847:
837:
833:
821:
746:
372:
252:
55:
36:
28:
24:
18:
1190:PCP theorem
1083:L-reduction
375:3-colorable
1360:1133.03001
1340:. p.
1304:0765.68036
1246:0897915917
1212:References
1180:) is also
840:is fixed.
1263:cite book
1039:…
1018:ℓ
1007:…
975:…
956:ϕ
953::
934:…
903:ℓ
892:…
703:¬
700:∨
678:¬
671:∧
643:¬
640:∨
618:¬
609:∧
583:¬
580:∨
558:¬
550:⟹
519:∧
489:∨
467:∨
434:∀
428:∀
414:∃
401:∃
388:∃
353:ϕ
331:ℓ
320:…
274:…
222:…
201:ℓ
190:…
158:…
139:ϕ
125:∀
122:…
109:∀
103:ℓ
95:∃
92:…
79:∃
60:(such as
29:Strict NP
1414:Category
1200:See also
1138:, hence
1121:complete
1102:MAX-3SAT
1255:9229294
31:) is a
1402:MaxSNP
1391:MaxSNP
1358:
1348:
1302:
1253:
1243:
1194:MaxSNP
1174:MaxSNP
1170:MaxSNP
1164:has a
1152:under
1150:MaxSNP
1140:MaxSNP
1136:MaxSNP
1125:MaxSNP
1106:MaxSNP
1095:MaxSNP
1089:, not
1079:MaxSNP
858:MaxSNP
844:MaxSNP
253:where
62:graphs
47:MaxSNP
27:(from
1251:S2CID
747:Here
1346:ISBN
1269:link
1241:ISBN
1186:P=NP
1380:SNP
1356:Zbl
1342:350
1300:Zbl
1292:doi
1231:doi
1206:APX
1182:APX
1162:APX
1158:APX
1145:APX
875:max
854:all
49:of
25:SNP
19:In
1416::
1400::
1389::
1378::
1354:.
1344:.
1324:;
1298:.
1288:43
1286:.
1265:}}
1261:{{
1249:.
1239:.
1127:.
370:.
53:.
38:NP
23:,
1404:0
1362:.
1306:.
1294::
1271:)
1257:.
1233::
1108:0
1097:0
1085:(
1062:|
1058:}
1055:)
1050:m
1046:v
1042:,
1036:,
1031:1
1027:v
1023:,
1014:S
1010:,
1004:,
999:1
995:S
991:,
986:k
982:R
978:,
972:,
967:1
963:R
959:(
950:)
945:m
941:v
937:,
931:,
926:1
922:v
918:(
915:{
911:|
899:S
895:,
889:,
884:1
880:S
860:0
838:k
834:k
822:k
806:3
802:S
798:,
793:2
789:S
785:,
780:1
776:S
755:E
730:)
725:)
722:)
719:v
716:(
711:3
707:S
697:)
694:u
691:(
686:3
682:S
675:(
666:)
662:)
659:v
656:(
651:2
647:S
637:)
634:u
631:(
626:2
622:S
614:(
605:)
602:)
599:v
596:(
591:1
587:S
577:)
574:u
571:(
566:1
562:S
555:(
545:)
542:v
539:,
536:u
533:(
530:E
525:(
513:)
508:)
505:u
502:(
497:3
493:S
486:)
483:u
480:(
475:2
471:S
464:)
461:u
458:(
453:1
449:S
443:(
437:v
431:u
422:3
418:S
409:2
405:S
396:1
392:S
327:S
323:,
317:,
312:1
308:S
285:k
281:R
277:,
271:,
266:1
262:R
238:)
233:m
229:v
225:,
219:,
214:1
210:v
206:,
197:S
193:,
187:,
182:1
178:S
174:,
169:k
165:R
161:,
155:,
150:1
146:R
142:(
133:m
129:v
117:1
113:v
99:S
87:1
83:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.