428:, that is, a truth assignment for which the input formulas fail to determine the function value. Its main idea is to first "clean" the decision problem instance, by removing redundant information and directly solving certain easy-to-solve cases of the problem. Then, in remaining cases it branches on a carefully chosen variable. This means recursively calling the same algorithm on two smaller subproblems, one for a restricted monotone function for which the variable has been set to true and the other in which the variable has been set to false. The cleaning step ensures the existence of a variable that belongs to many clauses, causing a significant reduction in the recursive subproblem size.
335:, one that takes a small amount of time per output clause. The decision, dualization, and exact learning formulations of the problem are all computationally equivalent, in the following sense: any one of them can be solved using a subroutine for any other of these problems, with a number of subroutine calls that is polynomial in the combined input and output sizes of the problems. Therefore, if any one of these problems could be solved in
357:
given function, have the same complexity. This problem can also be seen as a special case of the exact learning formulation of the problem. From a given CNF expression, it is straightforward to evaluate the function that it expresses. An exact learning algorithm will return both the starting CNF expression and the desired DNF expression. Therefore, dualization can be no harder than exact learning.
197:: given access to a subroutine for evaluating a monotone Boolean function, reconstruct both the CNF and DNF representations of the function, using a small number of function evaluations. However, it is crucial in analyzing the complexity of this problem that both the CNF and DNF representations are output. If only the CNF representation of an unknown monotone function is output, it follows from
701:
number of clauses. If that recursive call fails to find an inconsistency, then, instead of performing a single recursive call for the other branch, it performs one call for each clause that contains the branch variable, on a restricted subproblem in which all the other variables of that clause have been assigned in the same way. Its running time is an exponential function of
146:. However, this will transform the conjunctive normal form into disjunctive normal form, and vice versa, which may be undesired. Monotone dualization is the problem of finding an expression for the dual function without changing the form of the expression, or equivalently of converting a function in one normal form into the dual form.
819:
candidate clues that can eliminate each alternative solution. Thus, the enumeration of minimal hitting sets can be used to find all systems of clues that have a given solution. This approach has been as part of a computational proof that it is not possible to design a valid sudoku puzzle with only 16 clues.
201:
that the number of function evaluations must sometimes be exponential in the combined input and output sizes. This is because (to be sure of getting the correct answer) the algorithm must evaluate the function at least once for each prime implicate and at least once for each prime implicant, but this
384:
to the variables for which the function value is neither forced to be true by the known prime DNF clauses, nor forced to be false by the known prime CNF clauses. This construction may be performed by choosing values for the variables one at a time, at each step using the decision problem to preserve
124:
The disjunctive normal form of a monotone function expresses the function as a disjunction ("or") of clauses, each of which is a conjunction ("and") of variables. A conjunction may appear in the disjunctive normal form if it is false whenever the overall function is false; in this case, it is called
392:
Symmetrically, if the function evaluates to false, then try changing variables one at a time from false to true to find a maximal truth assignment for which the function still evaluates as false. This maximal truth assignment corresponds to a prime CNF clause, not already known; add this to the set
388:
Evaluate the function at this truth assignment. If it is true, then try changing variables one at a time from true to false to find a minimal truth assignment for which the function still evaluates as true. This minimal truth assignment corresponds to a prime DNF clause, not already known; add this
356:
The problem of finding the prime CNF expression for the dual function of a monotone function, given as a CNF formula, can be solved by finding the DNF expression for the given function and then dualizing it. Therefore, finding the dual CNF expression, and finding the DNF expression for the (primal)
449:
If any clause in one class uses a number of variables that is larger than the number of clauses in the other class, return that they are not dual. If this clauses is to be minimal, it cannot be the case that removing any one variable from it produces a valid clause for the same function, but there
399:
Each iteration through the outer loop of the algorithm uses a linear number of calls to the decision problem to find the unforced truth assignment, uses a linear number of function evaluations to find a minimal true or maximal false function value, and adds one clause to the output. Therefore, the
188:
of the family. A set cover is a subfamily with the same union as the whole family. If the sets in the given family are interpreted as vertices in a hypergraph, with each element of the sets interpreted as a hyperedge incident to the sets containing that element, then the minimal set covers are the
141:
The dual of a
Boolean function is obtained by negating all of its variables, applying the function, and then negating the result. The dual of the dual of any Boolean function is the original function. The dual of a monotone function is monotone. If one is given a monotone Boolean expression, then
104:
The conjunctive normal form of a monotone function expresses the function as a conjunction ("and") of clauses, each of which is a disjunction ("or") of some of the variables. A clause may appear in the conjunctive normal form if it is true whenever the overall function is true; in this case it is
700:
A second algorithm of
Fredman and Khachiyan has a similar overall structure, but in the case where the branch variable occurs in many clauses of one set and few of the other, it chooses the first of the two recursive calls to be the one where setting the branch variable significantly reduces the
360:
It is also straightforward to solve the decision problem given an algorithm for dualization: dualize the given CNF expression and then test whether it is equal to the given DNF expression. Therefore, research in this area has focused on the other direction of this equivalence: solving the exact
818:
puzzles, the problem of designing a system of clues that has a given grid of numbers as its unique solution can be formulated as a minimal hitting set problem. The 81 candidate clues from the given grid are the elements to be selected in the hitting set, and the sets to be hit are the sets of
803:, the enumeration of hitting sets has been used to identify subsets of metabolic reactions whose removal from a system adjusts the balance of the system in a desired direction. Analogous methods have also been applied to other biological interaction networks, for instance in the design of
180:
of the family. These are sets of elements that include at least one element from each set, and have no proper subset with the same property. If the sets in the given family are interpreted as hyperedges in a hypergraph, their minimal hitting sets are the hyperedges of the transversal
795:
of complex systems. From a collection of observations of faulty behavior of a system, each with some set of active components, one can surmise that the faulty components causing this misbehavior are likely to form a minimal hitting set of this family of sets.
438:
If the two sets of clauses (CNF and DNF in one version of the decision problem, or sets of CNF clauses that are supposed to represent two dual functions in another version) do not cover the same sets of variables, return that they are not
657:
When this algorithm branches on a variable occurring in many clauses, these clauses are eliminated from one of the two recursive calls. Using this fact, the running time of the algorithm can be bounded by an exponential function of
72:
to its arguments, and produces as output another truth value. It is monotone when changing an argument from false to true cannot change the output from true to false. Every monotone
Boolean function can be expressed as a
435:
Remove any clause that is not minimal among the given set of clauses. (That is, the removed clause uses a set of variables that is a superset of the variables in another clause of the same type.)
1306:
Elbassioni, Khaled M.; Hagen, Matthias; Rauf, Imran (2008), "Some fixed-parameter tractable classes of hypergraph duality and related problems", in Grohe, Martin; Niedermeier, Rolf (eds.),
377:
Use the decision problem to test whether the current sets of prime CNF and prime DNF clauses are dual, and if so terminate the algorithm, returning the clauses that have been found.
248:. The size of the output of the dualization and exact learning problems can be exponentially large, as a function of the number of variables or the input size. For instance, an
612:
variables. Each clause in the other set of clauses must have a non-empty intersection with this short clause, so one of the variables in the short clause occurs in at least a
738:
695:
651:
756:
Dualization of CNF or DNF formulas in which each variable appears in a bounded number of clauses, or exact learning of monotone functions that have formulas of this type.
610:
559:
In the remaining cases there exists a variable which occurs in a large fraction of one of the two sets of clauses. Branch on that variable. More precisely, if there are
553:
truth assignments that exist in total, then return that the two sets of clauses are not dual: at least one truth assignment must have a value that they do not determine.
446:
of variables, return that they are not dual. In this case, the clauses imply contradictory function values for any truth assignment that is consistent with both of them.
1423:
McGuire, Gary; Tugemann, Bastian; Civario, Gilles (2014), "There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem via hitting set enumeration",
484:
329:
551:
294:
577:
524:
504:
266:
230:
763:
hypergraphs, in which every induced sub-hypergraph has bounded average degree, and of hypergraphs for which generalizations of the graph-theoretic concepts of
169:. This is a hypergraph on the same vertex set that has a hyperedge for every minimal subset of vertices that touches all edges of the given hypergraph.
1493:
420:. Their algorithms directly solve the decision problem, but can be converted to the other forms of the monotone dualization problem as described in
1159:
Domingo, Carlos; Mishra, Nina; Pitt, Leonard (1999), "Efficient Read-Restricted
Monotone CNF/DNF dualization by learning with membership queries",
89:("not"). Such an expression is called a monotone Boolean expression. Every monotone Boolean expression describes a monotone Boolean function.
926:
109:, because the truth of the function implies the truth of the clause. This expression may be made canonical by restricting it to use only
792:
774:
Constructing transversal hypergraphs for which the complement (the hypergraph obtained by complementing each hyperedge) has low degree.
748:
Many special cases of the monotone dualization problem have been shown to be solvable in polynomial time through the analysis of their
1260:
Eiter, Thomas; Gottlob, Georg; Makino, Kazuhisa (2003), "New results on monotone dualization and generating hypergraph transversals",
400:
total number of calls to the decision problem and the total number of function evaluations is a polynomial of the total output size.
1333:
1197:
Proceedings of the Tenth Annual
Conference on Computational Learning Theory, COLT 1997, Nashville, Tennessee, USA, July 6-9, 1997
1473:
1308:
Parameterized and Exact
Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings
556:
If either set of clauses is empty, or both consist of only one clause, handle the problem as a special case in constant time.
133:, the implicants that use a minimal set of variables. The disjunctive normal form using only prime implicants is called the
924:
Gainer-Dewar, Andrew; Vera-Licona, Paola (2017), "The minimal hitting set generation problem: algorithms and computation",
129:, because its truth implies the truth of the function. This expression may be made canonical by restricting it to use only
976:
788:
194:
871:
Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008), "Computational aspects of monotone dualization: a brief survey",
142:
replacing all conjunctions by disjunctions produces another monotone
Boolean expression for the dual function, following
1081:
873:
453:
For each clause, count the number of truth assignments whose function value is determined by the clause. This number is
114:
17:
1224:; Gurvich, Vladimir; Elbassioni, Khaled (2007), "Computing many maximal independent sets for hypergraphs in parallel",
1226:
1029:
161:
424:. Alternatively, in cases where the answer to the decision problem is no, the algorithms can be modified to return a
156:
Convert the (prime) CNF expression of a function into the (prime) DNF expression for the same function, or vice versa
1387:
Haus, Utz-Uwe; Klamt, Steffen; Stephen, Tamon (April 2008), "Computing knock-out strategies in metabolic networks",
1488:
332:
431:
In more detail, the first and slower of the two algorithms of
Fredman and Khachiyan performs the following steps:
1478:
1262:
768:
1187:
Mishra, Nina; Pitt, Leonard (1997), "Generating all maximal independent sets of bounded-degree hypergraphs", in
1079:(1999), "On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions",
811:
749:
425:
800:
97:
93:
92:
There may be many different expressions for the same function. Among them are two special expressions, the
1359:
Klamt, Steffen; Gilles, Ernst Dieter (January 2004), "Minimal cut sets in biochemical reaction networks",
579:
total clauses, then (to cover all of the truth assignments) at least one of the clauses must have at most
371:
Initialize sets of the prime CNF and prime DNF clauses that have been identified so far, initially empty.
417:
340:
245:
53:
25:
385:
the property that the CNF and DNF clauses are non-dual when restricted to the chosen truth assignment.
1483:
227:
Is it possible to test whether two prime CNF expressions represent dual functions in polynomial time?
143:
82:
78:
36:. Equivalent problems can also be formulated as constructing the transversal hypergraph of a given
704:
661:
615:
1432:
1396:
1271:
1001:
935:
198:
149:
As a functional problem, monotone dualization can be expressed in the following equivalent ways:
74:
33:
582:
526:
variables. If the sum of these numbers, added over all clauses of both types, is fewer than the
1024:
331:
hyperedges in its transversal hypergraph. Therefore, what is desired for these problems is an
456:
299:
202:
number of evaluations can be exponentially larger than the number of prime implicates alone.
1442:
1406:
1368:
1342:
1311:
1281:
1235:
1217:
1200:
1168:
1134:
1122:
1086:
1076:
1048:
1038:
985:
945:
882:
413:
381:
206:
86:
1454:
1293:
1247:
1146:
1098:
1062:
997:
957:
896:
529:
361:
learning problem (or the dualization problem) given a subroutine for the decision problem.
216:
Test whether a prime CNF expression and a prime DNF expression represent the same function.
1450:
1289:
1243:
1192:
1142:
1118:
1094:
1058:
993:
953:
892:
409:
336:
241:
57:
29:
271:
153:
Given a (prime) CNF expression, construct a (prime) CNF expression for the dual function.
367:
outline the following algorithm for solving exact learning using a decision subroutine:
100:. For monotone functions these two special forms can also be restricted to be monotone:
1328:
562:
509:
489:
251:
173:
45:
1090:
1027:(1995), "Complexity of identification and dualization of positive Boolean functions",
1467:
1346:
784:
193:
Another version of the problem can be formulated as a problem of "exact learning" in
1373:
117:
of variables. The conjunctive normal form using only prime implicates is called the
1005:
443:
339:, they all could. However, the best time bound that is known for these problems is
237:
807:
experiments that can be used to infer protein interactions in biological systems.
244:
algorithm (in any of these equivalent forms). The fastest algorithms known run in
205:
It is also possible to express a variant of the monotone dualization problem as a
1446:
1315:
1125:(1996), "On the complexity of dualization of monotone disjunctive normal forms",
416:, is that monotone dualization (in any of its equivalent forms) can be solved in
1310:, Lecture Notes in Computer Science, vol. 5018, Springer, pp. 91–102,
1221:
1188:
177:
69:
56:
in the combined size of its input and output, but whether they can be solved in
41:
1285:
1239:
1173:
887:
804:
166:
37:
971:
764:
450:
are not enough clauses from the other class to block each of these removals.
343:. It remains an open problem whether they can be solved in polynomial time.
219:
185:
126:
49:
1138:
1043:
1410:
1204:
989:
949:
1053:
815:
1276:
940:
1437:
1401:
213:
Test whether two prime CNF expressions represent dual functions
1331:(April 1987), "A theory of diagnosis from first principles",
421:
1199:, Association for Computing Machinery, pp. 211–217,
352:
Equivalence of decision, enumeration, and exact learning
707:
664:
618:
585:
565:
532:
512:
492:
459:
302:
274:
254:
52:
of a family of sets. These problems can be solved in
1113:
1111:
1109:
1107:
1018:
1016:
1014:
68:A Boolean function takes as input an assignment of
732:
689:
645:
604:
571:
545:
518:
498:
478:
442:If two clauses from different sets of clauses use
408:A central result in the study of this problem, by
323:
288:
260:
783:One application of monotone dualization involves
866:
864:
862:
860:
858:
856:
854:
852:
184:Given a family of sets, generate all minimal
8:
919:
917:
915:
913:
911:
909:
907:
905:
850:
848:
846:
844:
842:
840:
838:
836:
834:
832:
422:§ Equivalence of different formulations
364:
231:(more unsolved problems in computer science)
1436:
1400:
1372:
1275:
1172:
1052:
1042:
939:
886:
724:
706:
681:
663:
631:
622:
617:
590:
584:
564:
537:
531:
511:
491:
464:
458:
311:
307:
301:
278:
273:
253:
189:hyperedges of the transversal hypergraph.
759:Constructing transversal hypergraphs of
828:
653:fraction of the other set of clauses.
7:
927:SIAM Journal on Discrete Mathematics
222:Unsolved problem in computer science
240:whether monotone dualization has a
14:
1494:Quasi-polynomial time algorithms
1389:Journal of Computational Biology
974:(1965), "On cliques in graphs",
721:
708:
678:
665:
1:
1374:10.1093/bioinformatics/btg395
1091:10.1016/S0166-218X(99)00099-2
977:Israel Journal of Mathematics
789:fault detection and isolation
195:computational learning theory
1447:10.1080/10586458.2013.870056
1347:10.1016/0004-3702(87)90062-2
1316:10.1007/978-3-540-79723-4_10
1082:Discrete Applied Mathematics
874:Discrete Applied Mathematics
733:{\displaystyle (\log n)^{2}}
690:{\displaystyle (\log n)^{3}}
646:{\displaystyle 1/\log _{2}m}
506:variables in a problem with
389:to the set of known clauses.
374:Repeat the following steps:
268:-vertex graph consisting of
113:, the implicates that use a
48:, or of listing all minimal
18:theoretical computer science
1227:Parallel Processing Letters
1030:Information and Computation
1510:
605:{\displaystyle \log _{2}m}
365:Bioch & Ibaraki (1995)
333:output-sensitive algorithm
1286:10.1137/S009753970240639X
1263:SIAM Journal on Computing
1240:10.1142/S0129626407002934
888:10.1016/j.dam.2007.04.017
209:, with a Boolean answer:
40:, of listing all minimal
34:monotone Boolean function
1425:Experimental Mathematics
812:recreational mathematics
750:parameterized complexity
744:Polynomial special cases
347:Computational complexity
1334:Artificial Intelligence
1174:10.1023/a:1007627028578
801:biochemical engineering
479:{\displaystyle 2^{n-k}}
324:{\displaystyle 3^{n/3}}
296:disjoint triangles has
176:, generate all minimal
98:disjunctive normal form
94:conjunctive normal form
85:("and"), without using
1474:Computational problems
1139:10.1006/jagm.1996.0062
1044:10.1006/inco.1995.1157
734:
691:
647:
606:
573:
547:
520:
500:
480:
325:
290:
262:
162:transversal hypergraph
1411:10.1089/cmb.2007.0229
1205:10.1145/267460.267500
1127:Journal of Algorithms
793:model-based diagnosis
735:
692:
648:
607:
574:
548:
546:{\displaystyle 2^{n}}
521:
501:
481:
418:quasi-polynomial time
404:Quasi-polynomial time
341:quasi-polynomial time
326:
291:
263:
246:quasi-polynomial time
54:quasi-polynomial time
26:computational problem
705:
662:
616:
583:
563:
530:
510:
490:
486:, for a clause with
457:
300:
272:
252:
60:is an open problem.
28:of constructing the
22:monotone dualization
1193:Schapire, Robert E.
1119:Fredman, Michael L.
814:, in the design of
289:{\displaystyle n/3}
83:logical conjunction
79:logical disjunction
1085:, 96/97: 363–373,
1025:Ibaraki, Toshihide
990:10.1007/BF02760024
950:10.1137/15M1055024
730:
687:
643:
602:
569:
543:
516:
496:
476:
321:
286:
258:
199:information theory
75:Boolean expression
1489:Covering problems
1218:Khachiyan, Leonid
1123:Khachiyan, Leonid
881:(11): 2035–2049,
752:. These include:
572:{\displaystyle m}
519:{\displaystyle n}
499:{\displaystyle k}
393:of known clauses.
261:{\displaystyle n}
1501:
1479:Families of sets
1458:
1457:
1440:
1420:
1414:
1413:
1404:
1384:
1378:
1377:
1376:
1356:
1350:
1349:
1325:
1319:
1318:
1303:
1297:
1296:
1279:
1257:
1251:
1250:
1214:
1208:
1207:
1184:
1178:
1177:
1176:
1161:Machine Learning
1156:
1150:
1149:
1115:
1102:
1101:
1072:
1066:
1065:
1056:
1046:
1020:
1009:
1008:
967:
961:
960:
943:
921:
900:
899:
890:
868:
761:uniformly sparse
739:
737:
736:
731:
729:
728:
696:
694:
693:
688:
686:
685:
652:
650:
649:
644:
636:
635:
626:
611:
609:
608:
603:
595:
594:
578:
576:
575:
570:
552:
550:
549:
544:
542:
541:
525:
523:
522:
517:
505:
503:
502:
497:
485:
483:
482:
477:
475:
474:
414:Leonid Khachiyan
382:truth assignment
330:
328:
327:
322:
320:
319:
315:
295:
293:
292:
287:
282:
267:
265:
264:
259:
223:
207:decision problem
144:De Morgan's laws
131:prime implicants
111:prime implicates
87:logical negation
1509:
1508:
1504:
1503:
1502:
1500:
1499:
1498:
1464:
1463:
1462:
1461:
1422:
1421:
1417:
1386:
1385:
1381:
1358:
1357:
1353:
1329:Reiter, Raymond
1327:
1326:
1322:
1305:
1304:
1300:
1259:
1258:
1254:
1216:
1215:
1211:
1186:
1185:
1181:
1158:
1157:
1153:
1117:
1116:
1105:
1074:
1073:
1069:
1023:Bioch, Jan C.;
1022:
1021:
1012:
969:
968:
964:
923:
922:
903:
870:
869:
830:
825:
781:
746:
720:
703:
702:
677:
660:
659:
627:
614:
613:
586:
581:
580:
561:
560:
533:
528:
527:
508:
507:
488:
487:
460:
455:
454:
410:Michael Fredman
406:
354:
349:
337:polynomial time
303:
298:
297:
270:
269:
250:
249:
242:polynomial time
234:
233:
228:
225:
221:
66:
58:polynomial time
12:
11:
5:
1507:
1505:
1497:
1496:
1491:
1486:
1481:
1476:
1466:
1465:
1460:
1459:
1431:(2): 190–217,
1415:
1395:(3): 259–268,
1379:
1367:(2): 226–234,
1361:Bioinformatics
1351:
1320:
1298:
1270:(2): 514–537,
1252:
1234:(2): 141–152,
1209:
1179:
1151:
1133:(3): 618–628,
1103:
1067:
1010:
962:
901:
827:
826:
824:
821:
780:
777:
776:
775:
772:
757:
745:
742:
727:
723:
719:
716:
713:
710:
684:
680:
676:
673:
670:
667:
655:
654:
642:
639:
634:
630:
625:
621:
601:
598:
593:
589:
568:
557:
554:
540:
536:
515:
495:
473:
470:
467:
463:
451:
447:
440:
436:
405:
402:
397:
396:
395:
394:
390:
386:
378:
372:
353:
350:
348:
345:
318:
314:
310:
306:
285:
281:
277:
257:
229:
226:
220:
218:
217:
214:
191:
190:
182:
174:family of sets
170:
159:Construct the
157:
154:
139:
138:
122:
65:
62:
46:family of sets
13:
10:
9:
6:
4:
3:
2:
1506:
1495:
1492:
1490:
1487:
1485:
1482:
1480:
1477:
1475:
1472:
1471:
1469:
1456:
1452:
1448:
1444:
1439:
1434:
1430:
1426:
1419:
1416:
1412:
1408:
1403:
1398:
1394:
1390:
1383:
1380:
1375:
1370:
1366:
1362:
1355:
1352:
1348:
1344:
1340:
1336:
1335:
1330:
1324:
1321:
1317:
1313:
1309:
1302:
1299:
1295:
1291:
1287:
1283:
1278:
1273:
1269:
1265:
1264:
1256:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1228:
1223:
1219:
1213:
1210:
1206:
1202:
1198:
1194:
1190:
1183:
1180:
1175:
1170:
1167:(1): 89–110,
1166:
1162:
1155:
1152:
1148:
1144:
1140:
1136:
1132:
1128:
1124:
1120:
1114:
1112:
1110:
1108:
1104:
1100:
1096:
1092:
1088:
1084:
1083:
1078:
1077:Khachiyan, L.
1075:Gurvich, V.;
1071:
1068:
1064:
1060:
1055:
1050:
1045:
1040:
1036:
1032:
1031:
1026:
1019:
1017:
1015:
1011:
1007:
1003:
999:
995:
991:
987:
983:
979:
978:
973:
970:Moon, J. W.;
966:
963:
959:
955:
951:
947:
942:
937:
934:(1): 63–100,
933:
929:
928:
920:
918:
916:
914:
912:
910:
908:
906:
902:
898:
894:
889:
884:
880:
876:
875:
867:
865:
863:
861:
859:
857:
855:
853:
851:
849:
847:
845:
843:
841:
839:
837:
835:
833:
829:
822:
820:
817:
813:
808:
806:
802:
797:
794:
790:
786:
785:group testing
778:
773:
770:
766:
762:
758:
755:
754:
753:
751:
743:
741:
725:
717:
714:
711:
698:
682:
674:
671:
668:
640:
637:
632:
628:
623:
619:
599:
596:
591:
587:
566:
558:
555:
538:
534:
513:
493:
471:
468:
465:
461:
452:
448:
445:
444:disjoint sets
441:
437:
434:
433:
432:
429:
427:
423:
419:
415:
411:
403:
401:
391:
387:
383:
379:
376:
375:
373:
370:
369:
368:
366:
362:
358:
351:
346:
344:
342:
338:
334:
316:
312:
308:
304:
283:
279:
275:
255:
247:
243:
239:
232:
215:
212:
211:
210:
208:
203:
200:
196:
187:
183:
179:
175:
171:
168:
164:
163:
158:
155:
152:
151:
150:
147:
145:
136:
132:
128:
123:
120:
116:
112:
108:
103:
102:
101:
99:
95:
90:
88:
84:
80:
76:
71:
63:
61:
59:
55:
51:
47:
43:
39:
35:
31:
27:
23:
19:
1428:
1424:
1418:
1392:
1388:
1382:
1364:
1360:
1354:
1341:(1): 57–95,
1338:
1332:
1323:
1307:
1301:
1267:
1261:
1255:
1231:
1225:
1222:Boros, Endre
1212:
1196:
1189:Freund, Yoav
1182:
1164:
1160:
1154:
1130:
1126:
1080:
1070:
1037:(1): 50–63,
1034:
1028:
981:
975:
965:
931:
925:
878:
872:
809:
798:
782:
779:Applications
771:are bounded.
760:
747:
699:
656:
430:
407:
398:
380:Construct a
363:
359:
355:
238:open problem
235:
204:
192:
178:hitting sets
160:
148:
140:
134:
130:
118:
110:
106:
91:
70:truth values
67:
42:hitting sets
21:
15:
1484:Hypergraphs
181:hypergraph.
165:of a given
115:minimal set
81:("or") and
77:using only
64:Definitions
1468:Categories
1277:cs/0204009
1054:1765/55247
941:1601.02939
823:References
805:microarray
769:degeneracy
186:set covers
167:hypergraph
105:called an
50:set covers
38:hypergraph
1438:1201.0749
1402:0801.0082
984:: 23–28,
972:Moser, L.
765:treewidth
715:
672:
638:
597:
469:−
236:It is an
135:prime DNF
127:implicant
119:prime CNF
107:implicate
1195:(eds.),
172:Given a
1455:3223774
1294:1969402
1248:2334718
1147:1417667
1099:1724731
1063:1358967
1006:9855414
998:0182577
958:3590650
897:2437000
791:in the
426:witness
1453:
1292:
1246:
1145:
1097:
1061:
1004:
996:
956:
895:
816:sudoku
1433:arXiv
1397:arXiv
1272:arXiv
1002:S2CID
936:arXiv
439:dual.
44:of a
32:of a
24:is a
787:for
412:and
96:and
30:dual
1443:doi
1407:doi
1369:doi
1343:doi
1312:doi
1282:doi
1236:doi
1201:doi
1169:doi
1135:doi
1087:doi
1049:hdl
1039:doi
1035:123
986:doi
946:doi
883:doi
879:156
810:In
799:In
767:or
712:log
669:log
629:log
588:log
125:an
16:In
1470::
1451:MR
1449:,
1441:,
1429:23
1427:,
1405:,
1393:15
1391:,
1365:20
1363:,
1339:32
1337:,
1290:MR
1288:,
1280:,
1268:32
1266:,
1244:MR
1242:,
1232:17
1230:,
1220:;
1191:;
1165:37
1163:,
1143:MR
1141:,
1131:21
1129:,
1121:;
1106:^
1095:MR
1093:,
1059:MR
1057:,
1047:,
1033:,
1013:^
1000:,
994:MR
992:,
980:,
954:MR
952:,
944:,
932:31
930:,
904:^
893:MR
891:,
877:,
831:^
740:.
697:.
20:,
1445::
1435::
1409::
1399::
1371::
1345::
1314::
1284::
1274::
1238::
1203::
1171::
1137::
1089::
1051::
1041::
988::
982:3
948::
938::
885::
726:2
722:)
718:n
709:(
683:3
679:)
675:n
666:(
641:m
633:2
624:/
620:1
600:m
592:2
567:m
539:n
535:2
514:n
494:k
472:k
466:n
462:2
317:3
313:/
309:n
305:3
284:3
280:/
276:n
256:n
224::
137:.
121:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.