4822:
114:. In this kind of reduction, a single hard instance of some other problem in #P is reduced to computing the permanent of a sequence of multiple graphs, each of which could potentially depend on the results of previous permanent computations. A later simplification by
3389:
The clause component is a weighted, directed graph with 7 nodes with edges weighted and nodes arranged to yield the properties specified above, and is given in
Appendix A of Ben-Dor and Halevi (1993). Note that the internal edges here have weights drawn from the set
130:
One reason for interest in the computational complexity of the permanent is that it provides an example of a problem where constructing a single solution can be done efficiently but where counting all solutions is hard. As
Papadimitriou writes in his book
426:, it is therefore sufficient to show that the number of satisfying assignments for a 3-CNF formula can be expressed succinctly as a function of the permanent of a matrix that contains only the values 0 and 1. This is usually accomplished in two steps:
5761:
4613:
3587:
The above section has shown that
Permanent is #P-hard. Through a series of reductions, any permanent can be reduced to the permanent of a matrix with entries only 0 or 1. This will prove that 01-Permanent is #P-hard as well.
1002:
The graph construction makes use of a component that is treated as a "black box." To keep the explanation simple, the properties of this component are given without actually defining the structure of the component.
5889:
5171:
4686:
3538:
4410:
4329:
3899:
3999:
5088:
39:
6415:
in such a case is for each node in the subgraph to take its self-loop. As each edge has a weight of one, the weight of the resulting cycle cover is equal to that of the original cycle cover.
3577:
527:
Through a series of reductions, reduce
Permanent to 01-Permanent, the problem of computing the permanent of a matrix all entries 0 or 1. This establishes that 01-permanent is #P-hard as well.
4898:
This fact is used to convert a non-negative matrix into an equivalent matrix whose entries are all powers of 2. The reduction can be expressed in terms of graphs equivalent to the matrices.
4812:
5768:
The objective here is to reduce a matrix whose entries are powers of 2 into an equivalent matrix containing only zeros and ones (i.e. a directed graph where each edge has a weight of 1).
4087:
3815:
928:
179:. Since any 0–1 matrix is the biadjacency matrix of some bipartite graph, Valiant's theorem implies that the problem of counting the number of perfect matchings in a bipartite graph is
6769:
Foundations of
Software Technology and Theoretical Computer Science: Proceedings of the 14th Conference, Madras, India, December 15–17, 1994. P. S. Thiagarajan (editor), pp. 256–275,
3944:
824:
4893:
4734:
3441:
877:
6127:
4498:
4259:
4187:
3171:, within each clause component is independent of the selection of sets of internal edges in other clause components, so one can multiply everything to get the weight of
281:
5920:
3737:
3042:
2985:
2911:
2778:
2010:
1943:
1878:
1449:
1372:
1192:
1058:
1031:
762:
729:
672:
621:
502:
475:
4768:
4035:
957:
6871:
6461:
6252:
6068:
5834:
5704:
5675:
5490:
5422:
5290:
5245:
4135:
3688:
3643:
2884:
1908:
6962:
5750:
4465:
3471:
3270:
2656:
1325:
1272:
699:
319:
6615:
6548:
6413:
6386:
6227:
6154:
6007:
3364:
3337:
3223:
3196:
3069:
3012:
2958:
2731:
2609:
2582:
2562:
2515:
2395:
2368:
2218:
2178:
2151:
2124:
2097:
2050:
1963:
1840:
1813:
1786:
1759:
1732:
1705:
1678:
1651:
1631:
1604:
1577:
1557:
1530:
1503:
1476:
1422:
1402:
1299:
1246:
1219:
1165:
1138:
1098:
977:
782:
645:
554:
522:
448:
4524:
3757:
4439:
6200:
6177:
5217:
6588:
6568:
6521:
6501:
6481:
6436:
6359:
6339:
6319:
6295:
6275:
6088:
6030:
5980:
5960:
5940:
5809:
5789:
5724:
5650:
5630:
5610:
5590:
5570:
5550:
5530:
5510:
5465:
5445:
5397:
5377:
5357:
5333:
5313:
5265:
5194:
4999:
4979:
4959:
4939:
4919:
4227:
4207:
4155:
4110:
3835:
3711:
3663:
3618:
3384:
3310:
3290:
3243:
3169:
3149:
3129:
3109:
3089:
2931:
2858:
2838:
2818:
2798:
2751:
2696:
2676:
2629:
2535:
2495:
2475:
2455:
2435:
2415:
2341:
2318:
2298:
2278:
2258:
2238:
2198:
2070:
2030:
1983:
1345:
1118:
1078:
997:
594:
574:
379:
359:
339:
6617:
possible cycle covers and since each path has a weight of 1, the sum of the weights of all these cycle covers equals the weight of the original cycle cover.
2584:
as well as each including edges going into and coming out of each clause component. Thus, these covers assign either true or false (but never both) to each
3091:, depends only on the internal edges involved. We add here the premise that the construction of the clause components is such that the sum over possible
5379:, then to cover all the nodes in the new sub graph, one must use the self-loops. Since all self-loops have a weight of 1, the weight of cycle-covers in
4532:
407:, such that the number of satisfying assignments of the Boolean formula is equal to the number of accepting paths of the NP machine. Any formula in SAT
1221:
is that it has three input edges and three output edges. The input edges come either from variable nodes or from previous clause components (e.g.,
5093:
17:
3476:
6712:
In: STACS, '99: 16th Annual
Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4–6, 1999 Proceedings. pp. 90–99.
6933:
4335:
6707:
6680:
5839:
4269:
194:
The computational complexity of the permanent also has some significance in other aspects of complexity theory: it is not known whether
4624:
3840:
6503:
in the subgraph. At each step down the subgraph there are two choices one can make to form such a path. One must make this choice
152:
85:, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even
5760:
4821:
1761:'s variable node. Of course, this completes the cycle. To create the F-cycle, one would follow the same procedure, but connect
6946:
6806:
6778:
6721:
6694:
5007:
3951:
6978:
2220:, any one that does induces exactly one assignment, and the same assignment induced depends only on the external edges of
2343:
that do not induce assignments are the ones with cycles that "jump" inside the clause components. That is, if for every
6764:
119:
3543:
6911:
6664:
3131:
is proper relative to the clause component, is 12. Otherwise the weight of the internal edges is 0. Since there are
6792:
4773:
3446:
Finally, since the sum of weights of all the sets of cycle covers inducing any particular satisfying assignment is
2753:
induces a satisfying assignment just in case its external edges satisfy certain properties. For any cycle cover of
4048:
7076:
3766:
882:
403:
problem (by definition), as any NP machine can be encoded into a
Boolean formula by a process similar to that in
66:
4618:
Note how the elements are non-negative because of the modular arithmetic. It is simple to compute the permanent
396:
143:
The PERMANENT problem for 0–1 matrices, which is equivalent to the problem of counting perfect matchings in a
504:(or equivalently, the permanent of its adjacency matrix) is equal to the number of satisfying assignments of
787:
7021:
W. Hartmann. On the complexity of immanants. Linear and
Multilinear Algebra 18 (1985), no. 2, pp. 127–140.
5247:
that has the same permanent as the original, one must show the correspondence between the cycle covers of
4839:
1910:, so the construction can be done in polytime (assuming that the clause components do not cause trouble).
198:
equals P (informally, whether every polynomially-solvable problem can be solved by a polylogarithmic-time
4694:
3906:
160:
2260:
is considered an incomplete cycle cover at this stage, because one talks only about its external edges,
1850:. Every external edge is part of a T-cycle or an F-cycle (but not both—that would force inconsistency).
415:
form preserving the number of satisfying assignments, and so #SAT and #3SAT are equivalent and #3SAT is
6901:
2611:
and ensure that each clause is satisfied. Further, the sets of cycle covers corresponding to all such
1707:
to the appropriate input edge of the next clause component, and so on. After the last clause in which
399:, is the problem of counting the number of satisfying assignments of a given Boolean formula. It is a
7009:
6965:
108:
5176:
This can be seen graphically in the Figure 1. The subgraph that replaces the existing edge contains
3393:
2698:. The reasons for this depend on the construction of the clause components, and are outlined below.
829:
1633:, and so on. Thence, draw an edge to the next clause component corresponding to the next clause of
6093:
7086:
5612:
different paths and sum of all these paths equal to the weight of the edge in the original graph
412:
382:
206:
has suggested an approach to resolving this question that relies on writing the permanent as the
58:
4470:
4232:
4160:
244:
7081:
6649:
3716:
3020:
2963:
2889:
2756:
1988:
1921:
1856:
1427:
1350:
1170:
1036:
1009:
738:
707:
650:
599:
480:
453:
107:
Valiant's definition of completeness, and his proof of completeness of 01-permanent, both used
4739:
4006:
1734:
appears, we connect the appropriate output edge of the corresponding clause component back to
933:
213:
Hartmann proved a generalization of
Valiant's theorem concerning the complexity of computing
6841:
6035:
4830:
2863:
1883:
78:
5729:
4444:
3449:
3248:
2634:
1304:
1251:
677:
294:
6889:
6593:
6526:
6391:
6364:
6205:
6132:
5985:
5811:-node directed graph where all the weights on edges are powers of two. Construct a graph,
3342:
3315:
3201:
3174:
3047:
2990:
2936:
2709:
2587:
2567:
2540:
2500:
2373:
2346:
2203:
2156:
2129:
2102:
2075:
2035:
1948:
1818:
1791:
1764:
1737:
1710:
1683:
1656:
1636:
1609:
1582:
1562:
1535:
1508:
1481:
1454:
1407:
1380:
1277:
1224:
1197:
1143:
1123:
1083:
962:
767:
630:
539:
507:
433:
214:
188:
62:
6816:
5894:
4503:
3742:
8:
4418:
93:
of counting the number of permutation matrices one can get by changing ones into zeroes.
6441:
6232:
6182:
6159:
5814:
5684:
5655:
5470:
5402:
5270:
5225:
5199:
4115:
3668:
3623:
1274:) and the output edges go either to variable nodes or to later clause components (e.g.,
6573:
6553:
6506:
6486:
6466:
6421:
6344:
6324:
6304:
6280:
6260:
6073:
6015:
5965:
5945:
5925:
5794:
5774:
5709:
5635:
5615:
5595:
5575:
5555:
5535:
5515:
5495:
5450:
5430:
5382:
5362:
5342:
5318:
5298:
5250:
5179:
4984:
4964:
4944:
4924:
4904:
4212:
4192:
4140:
4095:
3820:
3696:
3648:
3603:
3597:
3369:
3295:
3275:
3228:
3154:
3134:
3114:
3094:
3074:
2916:
2843:
2823:
2803:
2783:
2736:
2681:
2661:
2614:
2520:
2480:
2460:
2440:
2420:
2400:
2326:
2303:
2283:
2263:
2243:
2223:
2183:
2055:
2015:
1968:
1330:
1103:
1063:
982:
579:
559:
364:
344:
324:
199:
172:
54:
141:
are those for which the corresponding search problem can be solved in polynomial time.
6942:
6907:
6802:
6774:
6747:
6717:
6690:
6660:
1327:). The first input and output edges correspond with the first variable of the clause
404:
184:
122:, that translates the other problem into a single instance of the permanent problem.
7036:
6885:
6812:
6743:
423:
416:
400:
392:
284:
226:
180:
176:
175:
and the square of the number of perfect matchings is equal to the permanent of its
156:
111:
101:
86:
82:
7058:
4608:{\displaystyle A'=A{\bmod {1}}7={\begin{bmatrix}2&15\\15&1\end{bmatrix}}.}
6938:
6798:
6770:
6713:
4941:-node weighted directed graph with non-negative weights, where largest weight is
3111:-completions of the weight of the internal edges in each clause component, where
1846:, all of which have weight 1. Inside the clause components, the edges are termed
195:
155:(shown to be difficult by Valiant's results) is closely connected with finding a
144:
70:
7054:
7006:
7002:
6982:
6958:
6897:
6656:
6627:
381:
is equal to the sum of the weights of all cycle-covers of the graph; this is a
288:
203:
74:
2537:
contain either the complete T-cycle or the complete F-cycle of every variable
2300:-completions to show that one has a set of cycle covers corresponding to each
1842:'s variable node. All of these edges outside the clause components are termed
7070:
6829:
6760:
6686:
5001:
is converted into an equivalent edge with weights in powers of 2 as follows:
7038:
Proceedings of the 2nd Israel
Symposium on the Theory and Computing Systems
6929:
6833:
171:
vertices each, the number of perfect matchings equals the permanent of its
1194:
that functions as a sort of "black box." All that needs to be noted about
3473:, and the sum of weights of all other sets of cycle covers is 0, one has
207:
35:
6893:
6734:
Leslie G. Valiant (1979). "The Complexity of Computing the Permanent".
6676:
5166:{\displaystyle 0\leq x_{1}\leq x_{2}\leq \cdots \leq x_{r}\leq \log(w)}
3533:{\displaystyle \operatorname {Perm} (G_{\phi })=12^{m}\cdot (\#\phi )}
1347:, and so on. Thus far, all of the nodes that will appear in the graph
388:
4405:{\displaystyle \operatorname {Perm} (A)=2\cdot 1+(-2)\cdot (-2)=6.}
6797:. Algorithms and Computation in Mathematics. Vol. 7. Berlin:
6679:, James G. Williams, Rosalind Kent and Carolyn M. Hall (editors).
5884:{\displaystyle \operatorname {Perm} (G)=\operatorname {Perm} (G')}
4324:{\displaystyle A={\begin{bmatrix}2&-2\\-2&1\end{bmatrix}}}
4263:
An example of the transformation and why it works is given below.
1424:, one makes a true cycle (T-cycle) and a false cycle (F-cycle) in
159:
in a bipartite graph, which is solvable in polynomial time by the
118:
showed that it is possible to use a weaker notion of reduction, a
4681:{\displaystyle \operatorname {Perm} (A')=2\cdot 1+15\cdot 15=227}
2153:
that the assignment makes true, and vice versa for all variables
674:
where the sum of the weights of cycle covers in this set will be
97:
90:
3151:
clause components, and the selection of sets of internal edges,
3044:
was such that each external edge had weight 1, so the weight of
2180:
that the assignment makes false. Although any given cycle cover
1945:
is that its cycle covers correspond to variable assignments for
225:
Below, the proof that computing the permanent of a 01-matrix is
3894:{\displaystyle |\operatorname {Perm} (A)|\leq n!\cdot \mu ^{n}}
2706:
To understand the relevant properties of the clause components
826:. (Valiant's original proof constructs a graph with entries in
6906:(2nd ed.). MIT Press and McGraw-Hill. pp. 696–697.
4708:
4551:
3982:
3926:
1451:. To create the T-cycle, one starts at the variable node for
6630:
proved that the permanent is #P-hard using quantum methods.
7031:
Ben-Dor, Amir; Halevi, Shai (1993). "Zero-one permanent is
1680:
appears, connecting it from the appropriate output edge of
408:
6884:
3739:
integer matrix where no entry has a magnitude larger than
6794:
Completeness and reduction in algebraic complexity theory
2733:, one needs the notion of an M-completion. A cycle cover
139:
The most impressive and interesting #P-complete problems
7007:
Lower Bounds in a Parallel Model without Bit Operations.
6438:
is a part of the cycle cover then in any cycle cover of
596:
variables, one can construct a weighted, directed graph
217:
that generalize both the determinant and the permanent.
6766:
My Favorite Ten Complexity Theorems of the Past Decade.
5083:{\displaystyle w=2^{x_{1}}+2^{x_{2}}+\cdots +2^{x_{r}}}
2417:, and every output edge of the clause components is in
4571:
4284:
3994:{\displaystyle P=\operatorname {Perm} (A'){\bmod {Q}}}
1788:'s variable node to those clause components in which ~
1377:
Next, one would consider the edges. For each variable
477:, such that the sum of the weights of cycle covers of
6844:
6596:
6576:
6556:
6529:
6509:
6489:
6469:
6444:
6424:
6394:
6367:
6347:
6327:
6307:
6283:
6263:
6235:
6208:
6185:
6162:
6135:
6096:
6076:
6038:
6018:
5988:
5968:
5948:
5928:
5897:
5842:
5817:
5797:
5777:
5732:
5712:
5687:
5658:
5638:
5618:
5598:
5578:
5558:
5538:
5518:
5498:
5473:
5453:
5433:
5405:
5385:
5365:
5345:
5321:
5301:
5273:
5253:
5228:
5202:
5182:
5096:
5010:
4987:
4967:
4947:
4927:
4907:
4842:
4776:
4742:
4697:
4627:
4535:
4506:
4473:
4447:
4421:
4338:
4272:
4235:
4215:
4195:
4163:
4143:
4118:
4098:
4051:
4009:
3954:
3909:
3843:
3823:
3769:
3745:
3719:
3699:
3671:
3651:
3626:
3606:
3591:
3546:
3479:
3452:
3396:
3372:
3345:
3339:, so the product of the weights of internal edges in
3318:
3298:
3278:
3251:
3231:
3204:
3177:
3157:
3137:
3117:
3097:
3077:
3050:
3023:
2993:
2966:
2939:
2919:
2892:
2866:
2846:
2826:
2806:
2786:
2759:
2739:
2712:
2684:
2664:
2637:
2617:
2590:
2570:
2543:
2523:
2503:
2483:
2477:
is proper with respect to each clause component, and
2463:
2443:
2423:
2403:
2376:
2349:
2329:
2306:
2286:
2266:
2246:
2226:
2206:
2186:
2159:
2132:
2105:
2078:
2058:
2038:
2032:
induces an assignment of values for the variables in
2018:
1991:
1971:
1951:
1924:
1886:
1859:
1821:
1794:
1767:
1740:
1713:
1686:
1659:
1639:
1612:
1585:
1565:
1538:
1511:
1484:
1457:
1430:
1410:
1383:
1353:
1333:
1307:
1280:
1254:
1227:
1200:
1173:
1146:
1126:
1106:
1086:
1066:
1039:
1012:
985:
965:
936:
885:
832:
790:
770:
741:
710:
680:
653:
633:
602:
582:
562:
542:
510:
483:
456:
436:
367:
347:
327:
297:
247:
7059:
A Linear-Optical Proof that the Permanent is #P-Hard
6873:
Algorithm for Maximum Matchings in Bipartite Graphs.
6361:, one cannot create a path through the new subgraph
5592:. From the construction, one can see that there are
2820:
be a set of external edges. A set of internal edges
959:is "twice the number of occurrences of literals in
6865:
6609:
6582:
6562:
6542:
6515:
6495:
6475:
6455:
6430:
6407:
6380:
6353:
6333:
6313:
6289:
6269:
6246:
6221:
6194:
6171:
6148:
6121:
6082:
6062:
6024:
6001:
5974:
5954:
5934:
5914:
5883:
5828:
5803:
5783:
5744:
5718:
5698:
5669:
5644:
5624:
5604:
5584:
5564:
5544:
5524:
5504:
5484:
5459:
5439:
5416:
5391:
5371:
5351:
5327:
5307:
5284:
5259:
5239:
5211:
5188:
5165:
5082:
4993:
4973:
4953:
4933:
4913:
4887:
4806:
4762:
4728:
4680:
4607:
4518:
4492:
4459:
4433:
4404:
4323:
4253:
4221:
4201:
4181:
4149:
4129:
4104:
4081:
4029:
3993:
3938:
3893:
3829:
3809:
3751:
3731:
3705:
3682:
3657:
3637:
3612:
3571:
3532:
3465:
3435:
3378:
3358:
3331:
3304:
3284:
3264:
3237:
3217:
3190:
3163:
3143:
3123:
3103:
3083:
3063:
3036:
3006:
2979:
2952:
2925:
2905:
2878:
2852:
2832:
2812:
2792:
2772:
2745:
2725:
2690:
2670:
2650:
2623:
2603:
2576:
2556:
2529:
2509:
2489:
2469:
2449:
2429:
2409:
2389:
2362:
2335:
2312:
2292:
2272:
2252:
2232:
2212:
2192:
2172:
2145:
2118:
2091:
2064:
2044:
2024:
2004:
1977:
1957:
1937:
1913:
1902:
1872:
1834:
1807:
1780:
1753:
1726:
1699:
1672:
1645:
1625:
1598:
1571:
1551:
1524:
1497:
1470:
1443:
1416:
1396:
1366:
1339:
1319:
1293:
1266:
1240:
1213:
1186:
1159:
1132:
1112:
1092:
1072:
1052:
1025:
991:
971:
951:
922:
871:
818:
776:
756:
723:
693:
666:
639:
615:
588:
568:
548:
516:
496:
469:
442:
373:
353:
333:
313:
275:
27:Mathematical proof about the permanent of matrices
7012:, Volume 28 (1999), Issue 4, pp. 1460–1509.
6900:(2001) . "26.5: The relabel-to-front algorithm".
6733:
5764:Figure 2: Construction of a 01-matrix from 2Power
5632:. So the weight of corresponding cycle-covers in
4189:, since the number of bits required to represent
647:will have a corresponding set of cycle covers in
531:
7068:
5467:, then in all the corresponding cycle-covers in
5222:To prove that this produces an equivalent graph
3572:{\displaystyle \operatorname {Perm} (G_{\phi })}
321:representing the weight of the edge from vertex
6968:, Volume 20 (1991), Issue 5, pp. 865–877.
6963:PP is as Hard as the Polynomial-Time Hierarchy.
6012:This reduction is done locally at each edge in
2780:, consider only its external edges, the subset
383:graph-theoretic interpretation of the permanent
6229:has a weight of 1. Thus, the resulting graph
5962:where the maximal weight of any edge in graph
1505:that corresponds to the first clause in which
450:, construct a directed integer-weighted graph
7030:
4807:{\displaystyle \operatorname {Perm} (A)=P=6.}
3665:can be computed easily from the permanent of
2960:and the set of all resulting cycle covers of
2099:'s T-cycle and none of the external edges in
524:. This establishes that Permanent is #P-hard.
230:
229:is described. It mainly follows the proof by
220:
115:
4825:Figure 1: Construction of 2Power from NonNeg
4082:{\displaystyle \operatorname {Perm} (A)=P-Q}
3430:
3397:
1606:, this edge will be the first input edge of
866:
833:
764:is the number of satisfying assignments for
187:this implies that it is hard for the entire
6388:. The only way to form a cycle cover over
4816:
3810:{\displaystyle Q=2\cdot n!\cdot \mu ^{n}+1}
923:{\displaystyle 4^{t(\phi )}\cdot (\#\phi )}
3540:. The following section reduces computing
1033:, one first constructs a variable node in
81:of computing the permanent of a matrix is
6790:
6716:, New York, LLC Pub. Date: October 2007.
5836:, where the weight of each edge is 1 and
3930:
3924:
3292:does not induce a satisfying assignment,
2497:will produce a satisfying assignment for
1478:and draw an edge to the clause component
167:vertices partitioned into two parts with
6254:contains only edges with a weight of 1.
6202:edges as seen in Figure 2. Each edge in
2437:when the corresponding input edge is in
6925:
6923:
6706:Jin-Yi Cai, A. Pavan and D. Sivakumar,
3620:into an equivalent non-negative matrix
2701:
1559:is the first variable in the clause of
422:In order to prove that 01-Permanent is
96:Valiant's 1979 paper also introduced
14:
7069:
6935:The Design and Analysis of Algorithms.
3071:, the cycle covers resulting from any
2280:. In the section below, one considers
2072:contains all of the external edges in
784:, the permanent of this graph will be
6032:that has a weight larger than 1. Let
819:{\displaystyle 12^{m}\cdot (\#\phi )}
30:The correct title of this article is
6920:
6875:SIAM J. Comput. 2(4), 225–231 (1973)
6626:In 2011, quantum computer scientist
4888:{\displaystyle 13=2^{3}+2^{2}+2^{0}}
4831:decomposed into a sum of powers of 2
3245:induces a satisfying assignment, is
2320:that have the necessary properties.
1140:, one constructs a clause component
6878:
6645:
6643:
6621:
5755:
4729:{\displaystyle P=227{\bmod {1}}7=6}
3939:{\displaystyle A'=A\,{\bmod {\,}}Q}
3312:is not proper with respect to some
24:
6979:"1998 Gödel Prize. Seinosuke Toda"
5759:
4820:
3592:Reduction to a non-negative matrix
3521:
3443:; not all edges have 0–1 weights.
2200:need not induce an assignment for
911:
807:
745:
120:polynomial-time counting reduction
25:
7098:
3579:to the permanent of a 01 matrix.
2913:. Further, denote the set of all
65:, considered a seminal result in
6640:
6129:. It is replaced by a subgraph
2517:. This is because proper covers
1100:. Additionally, for each of the
89:, because it corresponds to the
7048:
7024:
7015:
6996:
6971:
6952:
5891:. The size of this new graph,
1914:Notable properties of the graph
731:will have weights summing to 0.
627:each satisfying assignment for
125:
67:computational complexity theory
47:#P-completeness of 01-permanent
32:#P-completeness of 01-permanent
6823:
6784:
6754:
6727:
6700:
6682:Encyclopedia of microcomputers
6670:
6057:
6045:
5909:
5898:
5878:
5867:
5855:
5849:
5160:
5154:
4789:
4783:
4645:
4634:
4393:
4384:
4378:
4369:
4351:
4345:
4248:
4242:
4176:
4170:
4064:
4058:
3978:
3967:
3865:
3861:
3855:
3845:
3566:
3553:
3527:
3518:
3499:
3486:
3436:{\displaystyle \{-1,0,1,2,3\}}
1896:
1888:
946:
940:
917:
908:
900:
894:
872:{\displaystyle \{-1,0,1,2,3\}}
813:
804:
751:
742:
532:Constructing the integer graph
397:Boolean satisfiability problem
270:
254:
163:. For a bipartite graph with 2
13:
1:
7035:-complete, a simpler proof".
6709:On the Hardness of Permanent.
6633:
2126:'s F-cycle for all variables
1815:appears, and finally back to
18:Permanent is sharp-P-complete
6748:10.1016/0304-3975(79)90044-6
6736:Theoretical Computer Science
6122:{\displaystyle w=2^{r}>1}
5492:, there must be a path from
4829:Note that any number can be
3600:, convert an integer matrix
3582:
3017:Recall that construction of
147:is the classic example here.
7:
236:
231:Ben-Dor & Halevi (1993)
116:Ben-Dor & Halevi (1993)
10:
7103:
6903:Introduction to Algorithms
6463:there must be a path from
6257:Consider some cycle-cover
5295:Consider some cycle-cover
4493:{\displaystyle \mu ^{n}=4}
4254:{\displaystyle \log(\mu )}
4182:{\displaystyle \log(\mu )}
704:all other cycle covers in
276:{\displaystyle A=(a_{ij})}
221:Ben-Dor and Halevi's proof
183:, and in conjunction with
34:. The substitution of the
29:
7010:SIAM Journal on Computing
6966:SIAM Journal on Computing
6791:Bürgisser, Peter (2000).
6654:Computational Complexity.
6650:Christos H. Papadimitriou
3732:{\displaystyle n\times n}
3645:so that the permanent of
3198:. So, the weight of each
3037:{\displaystyle G_{\phi }}
2980:{\displaystyle G_{\phi }}
2906:{\displaystyle G_{\phi }}
2860:-completion just in case
2773:{\displaystyle G_{\phi }}
2005:{\displaystyle G_{\phi }}
1938:{\displaystyle G_{\phi }}
1873:{\displaystyle G_{\phi }}
1444:{\displaystyle G_{\phi }}
1367:{\displaystyle G_{\phi }}
1187:{\displaystyle G_{\phi }}
1053:{\displaystyle G_{\phi }}
1026:{\displaystyle G_{\phi }}
757:{\displaystyle (\#\phi )}
724:{\displaystyle G_{\phi }}
667:{\displaystyle G_{\phi }}
616:{\displaystyle G_{\phi }}
497:{\displaystyle G_{\phi }}
470:{\displaystyle G_{\phi }}
361:. Then, the permanent of
6742:(2). Elsevier: 189–201.
6418:However, if the edge in
4817:Reduction to powers of 2
4763:{\displaystyle P<Q/2}
4030:{\displaystyle P<Q/2}
3837:is due to the fact that
952:{\displaystyle t(\phi )}
133:Computational Complexity
6866:{\displaystyle n^{5/2}}
6063:{\displaystyle e=(u,v)}
2879:{\displaystyle M\cup L}
1903:{\displaystyle |\phi |}
161:Hopcroft–Karp algorithm
153:computing the permanent
7077:Computational problems
6867:
6611:
6584:
6564:
6544:
6517:
6497:
6477:
6457:
6432:
6409:
6382:
6355:
6335:
6315:
6291:
6271:
6248:
6223:
6196:
6173:
6150:
6123:
6084:
6064:
6026:
6003:
5976:
5956:
5936:
5916:
5885:
5830:
5805:
5785:
5765:
5746:
5745:{\displaystyle \log W}
5720:
5700:
5681:Note that the size of
5671:
5646:
5626:
5606:
5586:
5572:are the nodes of edge
5566:
5546:
5526:
5506:
5486:
5461:
5441:
5418:
5393:
5373:
5353:
5329:
5309:
5286:
5261:
5241:
5213:
5190:
5167:
5084:
4995:
4975:
4955:
4935:
4915:
4889:
4826:
4808:
4764:
4730:
4682:
4609:
4520:
4494:
4461:
4460:{\displaystyle \mu =2}
4435:
4406:
4325:
4255:
4223:
4203:
4183:
4151:
4131:
4106:
4092:The transformation of
4083:
4031:
3995:
3940:
3895:
3831:
3811:
3753:
3733:
3707:
3684:
3659:
3639:
3614:
3573:
3534:
3467:
3466:{\displaystyle 12^{m}}
3437:
3380:
3360:
3333:
3306:
3286:
3266:
3265:{\displaystyle 12^{m}}
3239:
3219:
3192:
3165:
3145:
3125:
3105:
3085:
3065:
3038:
3008:
2981:
2954:
2927:
2907:
2880:
2854:
2834:
2814:
2794:
2774:
2747:
2727:
2692:
2672:
2652:
2651:{\displaystyle 12^{m}}
2625:
2605:
2578:
2558:
2531:
2511:
2491:
2471:
2451:
2431:
2411:
2391:
2364:
2337:
2314:
2294:
2274:
2254:
2234:
2214:
2194:
2174:
2147:
2120:
2093:
2066:
2046:
2026:
2006:
1979:
1959:
1939:
1904:
1874:
1836:
1809:
1782:
1755:
1728:
1701:
1674:
1647:
1627:
1600:
1573:
1553:
1526:
1499:
1472:
1445:
1418:
1398:
1368:
1341:
1321:
1320:{\displaystyle o>j}
1295:
1268:
1267:{\displaystyle i<j}
1242:
1215:
1188:
1161:
1134:
1114:
1094:
1074:
1054:
1027:
993:
973:
953:
924:
873:
820:
778:
758:
725:
695:
694:{\displaystyle 12^{m}}
668:
641:
617:
590:
570:
550:
518:
498:
471:
444:
430:Given a 3-CNF formula
375:
355:
335:
315:
314:{\displaystyle a_{ij}}
277:
149:
40:technical restrictions
6890:Leiserson, Charles E.
6868:
6612:
6610:{\displaystyle 2^{r}}
6585:
6565:
6545:
6543:{\displaystyle 2^{r}}
6518:
6498:
6478:
6458:
6433:
6410:
6408:{\displaystyle J_{e}}
6383:
6381:{\displaystyle J_{e}}
6356:
6336:
6316:
6292:
6272:
6249:
6224:
6222:{\displaystyle J_{e}}
6197:
6174:
6151:
6149:{\displaystyle J_{e}}
6124:
6085:
6065:
6027:
6004:
6002:{\displaystyle 2^{p}}
5977:
5957:
5937:
5917:
5886:
5831:
5806:
5786:
5763:
5747:
5721:
5701:
5672:
5647:
5627:
5607:
5587:
5567:
5547:
5527:
5507:
5487:
5462:
5442:
5419:
5394:
5374:
5354:
5330:
5310:
5287:
5262:
5242:
5214:
5191:
5168:
5085:
4996:
4976:
4956:
4936:
4916:
4890:
4824:
4809:
4765:
4731:
4683:
4610:
4521:
4495:
4462:
4436:
4407:
4326:
4256:
4224:
4204:
4184:
4152:
4132:
4107:
4084:
4032:
3996:
3941:
3896:
3832:
3812:
3754:
3734:
3708:
3685:
3660:
3640:
3615:
3574:
3535:
3468:
3438:
3381:
3361:
3359:{\displaystyle Z^{M}}
3334:
3332:{\displaystyle C_{j}}
3307:
3287:
3267:
3240:
3220:
3218:{\displaystyle Z^{M}}
3193:
3191:{\displaystyle Z^{M}}
3166:
3146:
3126:
3106:
3086:
3066:
3064:{\displaystyle Z^{M}}
3039:
3009:
3007:{\displaystyle Z^{M}}
2982:
2955:
2953:{\displaystyle L^{M}}
2928:
2908:
2881:
2855:
2835:
2815:
2795:
2775:
2748:
2728:
2726:{\displaystyle C_{j}}
2693:
2673:
2653:
2626:
2606:
2604:{\displaystyle x_{i}}
2579:
2577:{\displaystyle \phi }
2559:
2557:{\displaystyle x_{i}}
2532:
2512:
2510:{\displaystyle \phi }
2492:
2472:
2452:
2432:
2412:
2397:'s input edges is in
2392:
2390:{\displaystyle C_{j}}
2365:
2363:{\displaystyle C_{j}}
2338:
2315:
2295:
2275:
2255:
2235:
2215:
2213:{\displaystyle \phi }
2195:
2175:
2173:{\displaystyle x_{i}}
2148:
2146:{\displaystyle x_{i}}
2121:
2119:{\displaystyle x_{i}}
2094:
2092:{\displaystyle x_{i}}
2067:
2047:
2045:{\displaystyle \phi }
2027:
2007:
1980:
1960:
1958:{\displaystyle \phi }
1940:
1918:A useful property of
1905:
1880:is of size linear in
1875:
1837:
1835:{\displaystyle x_{i}}
1810:
1808:{\displaystyle x_{i}}
1783:
1781:{\displaystyle x_{i}}
1756:
1754:{\displaystyle x_{i}}
1729:
1727:{\displaystyle x_{i}}
1702:
1700:{\displaystyle C_{j}}
1675:
1673:{\displaystyle x_{i}}
1648:
1646:{\displaystyle \phi }
1628:
1626:{\displaystyle C_{j}}
1601:
1599:{\displaystyle C_{j}}
1574:
1572:{\displaystyle \phi }
1554:
1552:{\displaystyle x_{i}}
1527:
1525:{\displaystyle x_{i}}
1500:
1498:{\displaystyle C_{j}}
1473:
1471:{\displaystyle x_{i}}
1446:
1419:
1417:{\displaystyle \phi }
1399:
1397:{\displaystyle x_{i}}
1374:have been specified.
1369:
1342:
1322:
1296:
1294:{\displaystyle C_{i}}
1269:
1243:
1241:{\displaystyle C_{i}}
1216:
1214:{\displaystyle C_{j}}
1189:
1162:
1160:{\displaystyle C_{j}}
1135:
1133:{\displaystyle \phi }
1115:
1095:
1093:{\displaystyle \phi }
1075:
1055:
1028:
994:
974:
972:{\displaystyle \phi }
954:
925:
874:
821:
779:
777:{\displaystyle \phi }
759:
726:
696:
669:
642:
640:{\displaystyle \phi }
618:
591:
571:
551:
549:{\displaystyle \phi }
536:Given a 3CNF-formula
519:
517:{\displaystyle \phi }
499:
472:
445:
443:{\displaystyle \phi }
376:
356:
336:
316:
283:can be viewed as the
278:
215:immanants of matrices
137:
79:computational problem
49:, sometimes known as
6842:
6594:
6574:
6554:
6550:possible paths from
6527:
6523:times, resulting in
6507:
6487:
6467:
6442:
6422:
6392:
6365:
6345:
6325:
6305:
6301:If an original edge
6281:
6261:
6233:
6206:
6183:
6160:
6133:
6094:
6074:
6036:
6016:
5986:
5966:
5946:
5926:
5915:{\displaystyle (G')}
5895:
5840:
5815:
5795:
5775:
5730:
5710:
5685:
5656:
5636:
5616:
5596:
5576:
5556:
5536:
5516:
5496:
5471:
5451:
5431:
5403:
5383:
5363:
5343:
5319:
5299:
5271:
5251:
5226:
5200:
5180:
5094:
5008:
4985:
4965:
4945:
4925:
4905:
4840:
4774:
4740:
4695:
4625:
4533:
4519:{\displaystyle Q=17}
4504:
4471:
4445:
4419:
4336:
4270:
4233:
4213:
4193:
4161:
4141:
4116:
4096:
4049:
4007:
3952:
3907:
3841:
3821:
3767:
3752:{\displaystyle \mu }
3743:
3717:
3697:
3669:
3649:
3624:
3604:
3544:
3477:
3450:
3394:
3370:
3343:
3316:
3296:
3276:
3249:
3229:
3202:
3175:
3155:
3135:
3115:
3095:
3075:
3048:
3021:
2991:
2964:
2937:
2917:
2890:
2886:is a cycle cover of
2864:
2844:
2824:
2804:
2784:
2757:
2737:
2710:
2702:The clause component
2682:
2662:
2635:
2615:
2588:
2568:
2541:
2521:
2501:
2481:
2461:
2441:
2421:
2401:
2374:
2347:
2327:
2304:
2284:
2264:
2244:
2224:
2204:
2184:
2157:
2130:
2103:
2076:
2056:
2036:
2016:
1989:
1969:
1965:. For a cycle cover
1949:
1922:
1884:
1857:
1853:Note that the graph
1819:
1792:
1765:
1738:
1711:
1684:
1657:
1637:
1610:
1583:
1563:
1536:
1509:
1482:
1455:
1428:
1408:
1381:
1351:
1331:
1305:
1278:
1252:
1225:
1198:
1171:
1144:
1124:
1104:
1084:
1064:
1037:
1010:
983:
963:
934:
883:
830:
788:
768:
739:
708:
678:
651:
631:
600:
580:
560:
540:
508:
481:
454:
434:
365:
345:
325:
295:
245:
189:polynomial hierarchy
7044:. pp. 108–117.
6590:. Thus, there are
6156:that is made up of
5922:, is polynomial in
4434:{\displaystyle n=2}
2323:The sort of covers
2012:, one can say that
879:whose permanent is
6941:, New York, 1991.
6863:
6773:, New York, 2007.
6607:
6580:
6560:
6540:
6513:
6493:
6473:
6456:{\displaystyle G'}
6453:
6428:
6405:
6378:
6351:
6331:
6311:
6287:
6267:
6247:{\displaystyle G'}
6244:
6219:
6195:{\displaystyle 6r}
6192:
6172:{\displaystyle 2r}
6169:
6146:
6119:
6080:
6060:
6022:
5999:
5972:
5952:
5932:
5912:
5881:
5829:{\displaystyle G'}
5826:
5801:
5781:
5766:
5742:
5716:
5699:{\displaystyle G'}
5696:
5670:{\displaystyle G'}
5667:
5642:
5622:
5602:
5582:
5562:
5542:
5522:
5502:
5485:{\displaystyle G'}
5482:
5457:
5437:
5417:{\displaystyle R'}
5414:
5389:
5369:
5349:
5325:
5305:
5285:{\displaystyle G'}
5282:
5257:
5240:{\displaystyle G'}
5237:
5212:{\displaystyle 3r}
5209:
5186:
5163:
5080:
4991:
4971:
4951:
4931:
4911:
4885:
4827:
4804:
4760:
4726:
4678:
4605:
4596:
4516:
4490:
4457:
4431:
4402:
4321:
4315:
4251:
4219:
4199:
4179:
4147:
4130:{\displaystyle A'}
4127:
4102:
4079:
4027:
3991:
3936:
3891:
3827:
3807:
3749:
3729:
3703:
3683:{\displaystyle A'}
3680:
3655:
3638:{\displaystyle A'}
3635:
3610:
3598:modular arithmetic
3569:
3530:
3463:
3433:
3376:
3356:
3329:
3302:
3282:
3262:
3235:
3215:
3188:
3161:
3141:
3121:
3101:
3081:
3061:
3034:
3004:
2977:
2950:
2923:
2903:
2876:
2850:
2830:
2810:
2790:
2770:
2743:
2723:
2688:
2668:
2648:
2621:
2601:
2574:
2554:
2527:
2507:
2487:
2467:
2447:
2427:
2407:
2387:
2370:, at least one of
2360:
2333:
2310:
2290:
2270:
2250:
2230:
2210:
2190:
2170:
2143:
2116:
2089:
2062:
2042:
2022:
2002:
1975:
1955:
1935:
1900:
1870:
1832:
1805:
1778:
1751:
1724:
1697:
1670:
1643:
1623:
1596:
1569:
1549:
1522:
1495:
1468:
1441:
1414:
1394:
1364:
1337:
1317:
1291:
1264:
1238:
1211:
1184:
1157:
1130:
1110:
1090:
1070:
1050:
1023:
989:
969:
949:
920:
869:
816:
774:
754:
721:
691:
664:
637:
613:
586:
566:
546:
514:
494:
467:
440:
411:as a formula in 3-
371:
351:
331:
311:
273:
241:Any square matrix
200:parallel algorithm
173:biadjacency matrix
55:mathematical proof
6947:978-0-387-97687-7
6894:Rivest, Ronald L.
6886:Cormen, Thomas H.
6808:978-3-540-66752-0
6779:978-3-540-58715-6
6722:978-3-540-65691-3
6695:978-0-8247-2722-2
6583:{\displaystyle v}
6563:{\displaystyle u}
6516:{\displaystyle r}
6496:{\displaystyle v}
6476:{\displaystyle u}
6431:{\displaystyle G}
6354:{\displaystyle R}
6334:{\displaystyle G}
6314:{\displaystyle e}
6290:{\displaystyle G}
6270:{\displaystyle R}
6083:{\displaystyle G}
6025:{\displaystyle G}
5975:{\displaystyle G}
5955:{\displaystyle p}
5935:{\displaystyle n}
5804:{\displaystyle n}
5784:{\displaystyle G}
5719:{\displaystyle n}
5706:is polynomial in
5645:{\displaystyle G}
5625:{\displaystyle G}
5605:{\displaystyle r}
5585:{\displaystyle e}
5565:{\displaystyle v}
5545:{\displaystyle u}
5525:{\displaystyle v}
5505:{\displaystyle u}
5460:{\displaystyle R}
5440:{\displaystyle e}
5392:{\displaystyle R}
5372:{\displaystyle R}
5352:{\displaystyle e}
5328:{\displaystyle G}
5308:{\displaystyle R}
5260:{\displaystyle G}
5189:{\displaystyle r}
4994:{\displaystyle w}
4974:{\displaystyle e}
4954:{\displaystyle W}
4934:{\displaystyle n}
4914:{\displaystyle G}
4222:{\displaystyle n}
4209:is polynomial in
4202:{\displaystyle Q}
4150:{\displaystyle n}
4137:is polynomial in
4105:{\displaystyle A}
3830:{\displaystyle Q}
3706:{\displaystyle A}
3658:{\displaystyle A}
3613:{\displaystyle A}
3379:{\displaystyle 0}
3305:{\displaystyle M}
3285:{\displaystyle M}
3272:. Further, where
3238:{\displaystyle M}
3164:{\displaystyle L}
3144:{\displaystyle m}
3124:{\displaystyle M}
3104:{\displaystyle M}
3084:{\displaystyle M}
2926:{\displaystyle M}
2853:{\displaystyle M}
2833:{\displaystyle L}
2813:{\displaystyle M}
2793:{\displaystyle M}
2746:{\displaystyle Z}
2691:{\displaystyle 0}
2671:{\displaystyle Z}
2624:{\displaystyle Z}
2530:{\displaystyle Z}
2490:{\displaystyle Z}
2470:{\displaystyle Z}
2450:{\displaystyle Z}
2430:{\displaystyle Z}
2410:{\displaystyle Z}
2336:{\displaystyle Z}
2313:{\displaystyle M}
2293:{\displaystyle M}
2273:{\displaystyle M}
2253:{\displaystyle Z}
2233:{\displaystyle Z}
2193:{\displaystyle Z}
2065:{\displaystyle Z}
2025:{\displaystyle Z}
1978:{\displaystyle Z}
1579:corresponding to
1340:{\displaystyle j}
1113:{\displaystyle m}
1073:{\displaystyle n}
992:{\displaystyle m}
589:{\displaystyle n}
569:{\displaystyle m}
374:{\displaystyle A}
354:{\displaystyle j}
334:{\displaystyle i}
112:Turing reductions
51:Valiant's theorem
16:(Redirected from
7094:
7061:
7052:
7046:
7045:
7043:
7028:
7022:
7019:
7013:
7000:
6994:
6993:
6991:
6990:
6981:. Archived from
6975:
6969:
6956:
6950:
6927:
6918:
6917:
6882:
6876:
6872:
6870:
6869:
6864:
6862:
6861:
6857:
6830:John E. Hopcroft
6827:
6821:
6820:
6788:
6782:
6758:
6752:
6751:
6731:
6725:
6704:
6698:
6674:
6668:
6647:
6622:Aaronson's proof
6616:
6614:
6613:
6608:
6606:
6605:
6589:
6587:
6586:
6581:
6569:
6567:
6566:
6561:
6549:
6547:
6546:
6541:
6539:
6538:
6522:
6520:
6519:
6514:
6502:
6500:
6499:
6494:
6482:
6480:
6479:
6474:
6462:
6460:
6459:
6454:
6452:
6437:
6435:
6434:
6429:
6414:
6412:
6411:
6406:
6404:
6403:
6387:
6385:
6384:
6379:
6377:
6376:
6360:
6358:
6357:
6352:
6340:
6338:
6337:
6332:
6320:
6318:
6317:
6312:
6296:
6294:
6293:
6288:
6276:
6274:
6273:
6268:
6253:
6251:
6250:
6245:
6243:
6228:
6226:
6225:
6220:
6218:
6217:
6201:
6199:
6198:
6193:
6178:
6176:
6175:
6170:
6155:
6153:
6152:
6147:
6145:
6144:
6128:
6126:
6125:
6120:
6112:
6111:
6089:
6087:
6086:
6081:
6069:
6067:
6066:
6061:
6031:
6029:
6028:
6023:
6008:
6006:
6005:
6000:
5998:
5997:
5981:
5979:
5978:
5973:
5961:
5959:
5958:
5953:
5941:
5939:
5938:
5933:
5921:
5919:
5918:
5913:
5908:
5890:
5888:
5887:
5882:
5877:
5835:
5833:
5832:
5827:
5825:
5810:
5808:
5807:
5802:
5790:
5788:
5787:
5782:
5756:Reduction to 0–1
5751:
5749:
5748:
5743:
5725:
5723:
5722:
5717:
5705:
5703:
5702:
5697:
5695:
5676:
5674:
5673:
5668:
5666:
5651:
5649:
5648:
5643:
5631:
5629:
5628:
5623:
5611:
5609:
5608:
5603:
5591:
5589:
5588:
5583:
5571:
5569:
5568:
5563:
5551:
5549:
5548:
5543:
5531:
5529:
5528:
5523:
5511:
5509:
5508:
5503:
5491:
5489:
5488:
5483:
5481:
5466:
5464:
5463:
5458:
5446:
5444:
5443:
5438:
5423:
5421:
5420:
5415:
5413:
5398:
5396:
5395:
5390:
5378:
5376:
5375:
5370:
5358:
5356:
5355:
5350:
5334:
5332:
5331:
5326:
5314:
5312:
5311:
5306:
5291:
5289:
5288:
5283:
5281:
5266:
5264:
5263:
5258:
5246:
5244:
5243:
5238:
5236:
5218:
5216:
5215:
5210:
5195:
5193:
5192:
5187:
5172:
5170:
5169:
5164:
5144:
5143:
5125:
5124:
5112:
5111:
5089:
5087:
5086:
5081:
5079:
5078:
5077:
5076:
5053:
5052:
5051:
5050:
5033:
5032:
5031:
5030:
5000:
4998:
4997:
4992:
4980:
4978:
4977:
4972:
4960:
4958:
4957:
4952:
4940:
4938:
4937:
4932:
4920:
4918:
4917:
4912:
4894:
4892:
4891:
4886:
4884:
4883:
4871:
4870:
4858:
4857:
4813:
4811:
4810:
4805:
4769:
4767:
4766:
4761:
4756:
4735:
4733:
4732:
4727:
4716:
4715:
4687:
4685:
4684:
4679:
4644:
4614:
4612:
4611:
4606:
4601:
4600:
4559:
4558:
4543:
4525:
4523:
4522:
4517:
4499:
4497:
4496:
4491:
4483:
4482:
4466:
4464:
4463:
4458:
4440:
4438:
4437:
4432:
4411:
4409:
4408:
4403:
4330:
4328:
4327:
4322:
4320:
4319:
4260:
4258:
4257:
4252:
4228:
4226:
4225:
4220:
4208:
4206:
4205:
4200:
4188:
4186:
4185:
4180:
4156:
4154:
4153:
4148:
4136:
4134:
4133:
4128:
4126:
4111:
4109:
4108:
4103:
4088:
4086:
4085:
4080:
4036:
4034:
4033:
4028:
4023:
4000:
3998:
3997:
3992:
3990:
3989:
3977:
3945:
3943:
3942:
3937:
3932:
3931:
3917:
3900:
3898:
3897:
3892:
3890:
3889:
3868:
3848:
3836:
3834:
3833:
3828:
3817:. The choice of
3816:
3814:
3813:
3808:
3800:
3799:
3758:
3756:
3755:
3750:
3738:
3736:
3735:
3730:
3712:
3710:
3709:
3704:
3689:
3687:
3686:
3681:
3679:
3664:
3662:
3661:
3656:
3644:
3642:
3641:
3636:
3634:
3619:
3617:
3616:
3611:
3578:
3576:
3575:
3570:
3565:
3564:
3539:
3537:
3536:
3531:
3514:
3513:
3498:
3497:
3472:
3470:
3469:
3464:
3462:
3461:
3442:
3440:
3439:
3434:
3385:
3383:
3382:
3377:
3365:
3363:
3362:
3357:
3355:
3354:
3338:
3336:
3335:
3330:
3328:
3327:
3311:
3309:
3308:
3303:
3291:
3289:
3288:
3283:
3271:
3269:
3268:
3263:
3261:
3260:
3244:
3242:
3241:
3236:
3224:
3222:
3221:
3216:
3214:
3213:
3197:
3195:
3194:
3189:
3187:
3186:
3170:
3168:
3167:
3162:
3150:
3148:
3147:
3142:
3130:
3128:
3127:
3122:
3110:
3108:
3107:
3102:
3090:
3088:
3087:
3082:
3070:
3068:
3067:
3062:
3060:
3059:
3043:
3041:
3040:
3035:
3033:
3032:
3013:
3011:
3010:
3005:
3003:
3002:
2986:
2984:
2983:
2978:
2976:
2975:
2959:
2957:
2956:
2951:
2949:
2948:
2933:-completions by
2932:
2930:
2929:
2924:
2912:
2910:
2909:
2904:
2902:
2901:
2885:
2883:
2882:
2877:
2859:
2857:
2856:
2851:
2839:
2837:
2836:
2831:
2819:
2817:
2816:
2811:
2799:
2797:
2796:
2791:
2779:
2777:
2776:
2771:
2769:
2768:
2752:
2750:
2749:
2744:
2732:
2730:
2729:
2724:
2722:
2721:
2697:
2695:
2694:
2689:
2677:
2675:
2674:
2669:
2658:, and any other
2657:
2655:
2654:
2649:
2647:
2646:
2630:
2628:
2627:
2622:
2610:
2608:
2607:
2602:
2600:
2599:
2583:
2581:
2580:
2575:
2563:
2561:
2560:
2555:
2553:
2552:
2536:
2534:
2533:
2528:
2516:
2514:
2513:
2508:
2496:
2494:
2493:
2488:
2476:
2474:
2473:
2468:
2456:
2454:
2453:
2448:
2436:
2434:
2433:
2428:
2416:
2414:
2413:
2408:
2396:
2394:
2393:
2388:
2386:
2385:
2369:
2367:
2366:
2361:
2359:
2358:
2342:
2340:
2339:
2334:
2319:
2317:
2316:
2311:
2299:
2297:
2296:
2291:
2279:
2277:
2276:
2271:
2259:
2257:
2256:
2251:
2239:
2237:
2236:
2231:
2219:
2217:
2216:
2211:
2199:
2197:
2196:
2191:
2179:
2177:
2176:
2171:
2169:
2168:
2152:
2150:
2149:
2144:
2142:
2141:
2125:
2123:
2122:
2117:
2115:
2114:
2098:
2096:
2095:
2090:
2088:
2087:
2071:
2069:
2068:
2063:
2051:
2049:
2048:
2043:
2031:
2029:
2028:
2023:
2011:
2009:
2008:
2003:
2001:
2000:
1984:
1982:
1981:
1976:
1964:
1962:
1961:
1956:
1944:
1942:
1941:
1936:
1934:
1933:
1909:
1907:
1906:
1901:
1899:
1891:
1879:
1877:
1876:
1871:
1869:
1868:
1841:
1839:
1838:
1833:
1831:
1830:
1814:
1812:
1811:
1806:
1804:
1803:
1787:
1785:
1784:
1779:
1777:
1776:
1760:
1758:
1757:
1752:
1750:
1749:
1733:
1731:
1730:
1725:
1723:
1722:
1706:
1704:
1703:
1698:
1696:
1695:
1679:
1677:
1676:
1671:
1669:
1668:
1652:
1650:
1649:
1644:
1632:
1630:
1629:
1624:
1622:
1621:
1605:
1603:
1602:
1597:
1595:
1594:
1578:
1576:
1575:
1570:
1558:
1556:
1555:
1550:
1548:
1547:
1531:
1529:
1528:
1523:
1521:
1520:
1504:
1502:
1501:
1496:
1494:
1493:
1477:
1475:
1474:
1469:
1467:
1466:
1450:
1448:
1447:
1442:
1440:
1439:
1423:
1421:
1420:
1415:
1403:
1401:
1400:
1395:
1393:
1392:
1373:
1371:
1370:
1365:
1363:
1362:
1346:
1344:
1343:
1338:
1326:
1324:
1323:
1318:
1300:
1298:
1297:
1292:
1290:
1289:
1273:
1271:
1270:
1265:
1247:
1245:
1244:
1239:
1237:
1236:
1220:
1218:
1217:
1212:
1210:
1209:
1193:
1191:
1190:
1185:
1183:
1182:
1166:
1164:
1163:
1158:
1156:
1155:
1139:
1137:
1136:
1131:
1119:
1117:
1116:
1111:
1099:
1097:
1096:
1091:
1079:
1077:
1076:
1071:
1060:for each of the
1059:
1057:
1056:
1051:
1049:
1048:
1032:
1030:
1029:
1024:
1022:
1021:
998:
996:
995:
990:
978:
976:
975:
970:
958:
956:
955:
950:
929:
927:
926:
921:
904:
903:
878:
876:
875:
870:
825:
823:
822:
817:
800:
799:
783:
781:
780:
775:
763:
761:
760:
755:
730:
728:
727:
722:
720:
719:
700:
698:
697:
692:
690:
689:
673:
671:
670:
665:
663:
662:
646:
644:
643:
638:
622:
620:
619:
614:
612:
611:
595:
593:
592:
587:
575:
573:
572:
567:
555:
553:
552:
547:
523:
521:
520:
515:
503:
501:
500:
495:
493:
492:
476:
474:
473:
468:
466:
465:
449:
447:
446:
441:
409:can be rewritten
393:function problem
380:
378:
377:
372:
360:
358:
357:
352:
340:
338:
337:
332:
320:
318:
317:
312:
310:
309:
285:adjacency matrix
282:
280:
279:
274:
269:
268:
177:adjacency matrix
157:perfect matching
102:complexity class
77:proved that the
21:
7102:
7101:
7097:
7096:
7095:
7093:
7092:
7091:
7067:
7066:
7065:
7064:
7053:
7049:
7041:
7029:
7025:
7020:
7016:
7001:
6997:
6988:
6986:
6977:
6976:
6972:
6957:
6953:
6939:Springer-Verlag
6928:
6921:
6914:
6898:Stein, Clifford
6883:
6879:
6853:
6849:
6845:
6843:
6840:
6839:
6834:Richard M. Karp
6828:
6824:
6809:
6799:Springer-Verlag
6789:
6785:
6771:Springer-Verlag
6759:
6755:
6732:
6728:
6714:Springer-Verlag
6705:
6701:
6675:
6671:
6648:
6641:
6636:
6624:
6601:
6597:
6595:
6592:
6591:
6575:
6572:
6571:
6555:
6552:
6551:
6534:
6530:
6528:
6525:
6524:
6508:
6505:
6504:
6488:
6485:
6484:
6468:
6465:
6464:
6445:
6443:
6440:
6439:
6423:
6420:
6419:
6399:
6395:
6393:
6390:
6389:
6372:
6368:
6366:
6363:
6362:
6346:
6343:
6342:
6326:
6323:
6322:
6306:
6303:
6302:
6282:
6279:
6278:
6262:
6259:
6258:
6236:
6234:
6231:
6230:
6213:
6209:
6207:
6204:
6203:
6184:
6181:
6180:
6161:
6158:
6157:
6140:
6136:
6134:
6131:
6130:
6107:
6103:
6095:
6092:
6091:
6075:
6072:
6071:
6037:
6034:
6033:
6017:
6014:
6013:
5993:
5989:
5987:
5984:
5983:
5967:
5964:
5963:
5947:
5944:
5943:
5927:
5924:
5923:
5901:
5896:
5893:
5892:
5870:
5841:
5838:
5837:
5818:
5816:
5813:
5812:
5796:
5793:
5792:
5776:
5773:
5772:
5758:
5731:
5728:
5727:
5711:
5708:
5707:
5688:
5686:
5683:
5682:
5659:
5657:
5654:
5653:
5637:
5634:
5633:
5617:
5614:
5613:
5597:
5594:
5593:
5577:
5574:
5573:
5557:
5554:
5553:
5537:
5534:
5533:
5517:
5514:
5513:
5497:
5494:
5493:
5474:
5472:
5469:
5468:
5452:
5449:
5448:
5432:
5429:
5428:
5406:
5404:
5401:
5400:
5384:
5381:
5380:
5364:
5361:
5360:
5344:
5341:
5340:
5320:
5317:
5316:
5300:
5297:
5296:
5274:
5272:
5269:
5268:
5252:
5249:
5248:
5229:
5227:
5224:
5223:
5201:
5198:
5197:
5181:
5178:
5177:
5139:
5135:
5120:
5116:
5107:
5103:
5095:
5092:
5091:
5072:
5068:
5067:
5063:
5046:
5042:
5041:
5037:
5026:
5022:
5021:
5017:
5009:
5006:
5005:
4986:
4983:
4982:
4966:
4963:
4962:
4946:
4943:
4942:
4926:
4923:
4922:
4906:
4903:
4902:
4879:
4875:
4866:
4862:
4853:
4849:
4841:
4838:
4837:
4833:. For example,
4819:
4775:
4772:
4771:
4752:
4741:
4738:
4737:
4711:
4707:
4696:
4693:
4692:
4637:
4626:
4623:
4622:
4595:
4594:
4589:
4583:
4582:
4577:
4567:
4566:
4554:
4550:
4536:
4534:
4531:
4530:
4505:
4502:
4501:
4478:
4474:
4472:
4469:
4468:
4446:
4443:
4442:
4420:
4417:
4416:
4337:
4334:
4333:
4314:
4313:
4308:
4299:
4298:
4290:
4280:
4279:
4271:
4268:
4267:
4234:
4231:
4230:
4214:
4211:
4210:
4194:
4191:
4190:
4162:
4159:
4158:
4142:
4139:
4138:
4119:
4117:
4114:
4113:
4097:
4094:
4093:
4050:
4047:
4046:
4019:
4008:
4005:
4004:
3985:
3981:
3970:
3953:
3950:
3949:
3929:
3925:
3910:
3908:
3905:
3904:
3885:
3881:
3864:
3844:
3842:
3839:
3838:
3822:
3819:
3818:
3795:
3791:
3768:
3765:
3764:
3744:
3741:
3740:
3718:
3715:
3714:
3698:
3695:
3694:
3672:
3670:
3667:
3666:
3650:
3647:
3646:
3627:
3625:
3622:
3621:
3605:
3602:
3601:
3594:
3585:
3560:
3556:
3545:
3542:
3541:
3509:
3505:
3493:
3489:
3478:
3475:
3474:
3457:
3453:
3451:
3448:
3447:
3395:
3392:
3391:
3371:
3368:
3367:
3350:
3346:
3344:
3341:
3340:
3323:
3319:
3317:
3314:
3313:
3297:
3294:
3293:
3277:
3274:
3273:
3256:
3252:
3250:
3247:
3246:
3230:
3227:
3226:
3209:
3205:
3203:
3200:
3199:
3182:
3178:
3176:
3173:
3172:
3156:
3153:
3152:
3136:
3133:
3132:
3116:
3113:
3112:
3096:
3093:
3092:
3076:
3073:
3072:
3055:
3051:
3049:
3046:
3045:
3028:
3024:
3022:
3019:
3018:
2998:
2994:
2992:
2989:
2988:
2971:
2967:
2965:
2962:
2961:
2944:
2940:
2938:
2935:
2934:
2918:
2915:
2914:
2897:
2893:
2891:
2888:
2887:
2865:
2862:
2861:
2845:
2842:
2841:
2825:
2822:
2821:
2805:
2802:
2801:
2785:
2782:
2781:
2764:
2760:
2758:
2755:
2754:
2738:
2735:
2734:
2717:
2713:
2711:
2708:
2707:
2704:
2683:
2680:
2679:
2663:
2660:
2659:
2642:
2638:
2636:
2633:
2632:
2616:
2613:
2612:
2595:
2591:
2589:
2586:
2585:
2569:
2566:
2565:
2548:
2544:
2542:
2539:
2538:
2522:
2519:
2518:
2502:
2499:
2498:
2482:
2479:
2478:
2462:
2459:
2458:
2442:
2439:
2438:
2422:
2419:
2418:
2402:
2399:
2398:
2381:
2377:
2375:
2372:
2371:
2354:
2350:
2348:
2345:
2344:
2328:
2325:
2324:
2305:
2302:
2301:
2285:
2282:
2281:
2265:
2262:
2261:
2245:
2242:
2241:
2225:
2222:
2221:
2205:
2202:
2201:
2185:
2182:
2181:
2164:
2160:
2158:
2155:
2154:
2137:
2133:
2131:
2128:
2127:
2110:
2106:
2104:
2101:
2100:
2083:
2079:
2077:
2074:
2073:
2057:
2054:
2053:
2037:
2034:
2033:
2017:
2014:
2013:
1996:
1992:
1990:
1987:
1986:
1970:
1967:
1966:
1950:
1947:
1946:
1929:
1925:
1923:
1920:
1919:
1916:
1895:
1887:
1885:
1882:
1881:
1864:
1860:
1858:
1855:
1854:
1826:
1822:
1820:
1817:
1816:
1799:
1795:
1793:
1790:
1789:
1772:
1768:
1766:
1763:
1762:
1745:
1741:
1739:
1736:
1735:
1718:
1714:
1712:
1709:
1708:
1691:
1687:
1685:
1682:
1681:
1664:
1660:
1658:
1655:
1654:
1638:
1635:
1634:
1617:
1613:
1611:
1608:
1607:
1590:
1586:
1584:
1581:
1580:
1564:
1561:
1560:
1543:
1539:
1537:
1534:
1533:
1516:
1512:
1510:
1507:
1506:
1489:
1485:
1483:
1480:
1479:
1462:
1458:
1456:
1453:
1452:
1435:
1431:
1429:
1426:
1425:
1409:
1406:
1405:
1388:
1384:
1382:
1379:
1378:
1358:
1354:
1352:
1349:
1348:
1332:
1329:
1328:
1306:
1303:
1302:
1285:
1281:
1279:
1276:
1275:
1253:
1250:
1249:
1232:
1228:
1226:
1223:
1222:
1205:
1201:
1199:
1196:
1195:
1178:
1174:
1172:
1169:
1168:
1151:
1147:
1145:
1142:
1141:
1125:
1122:
1121:
1105:
1102:
1101:
1085:
1082:
1081:
1065:
1062:
1061:
1044:
1040:
1038:
1035:
1034:
1017:
1013:
1011:
1008:
1007:
984:
981:
980:
964:
961:
960:
935:
932:
931:
890:
886:
884:
881:
880:
831:
828:
827:
795:
791:
789:
786:
785:
769:
766:
765:
740:
737:
736:
715:
711:
709:
706:
705:
685:
681:
679:
676:
675:
658:
654:
652:
649:
648:
632:
629:
628:
607:
603:
601:
598:
597:
581:
578:
577:
561:
558:
557:
541:
538:
537:
534:
509:
506:
505:
488:
484:
482:
479:
478:
461:
457:
455:
452:
451:
435:
432:
431:
395:related to the
366:
363:
362:
346:
343:
342:
326:
323:
322:
302:
298:
296:
293:
292:
261:
257:
246:
243:
242:
239:
223:
145:bipartite graph
128:
109:polynomial-time
71:scholarly paper
43:
28:
23:
22:
15:
12:
11:
5:
7100:
7090:
7089:
7087:Article proofs
7084:
7079:
7063:
7062:
7047:
7023:
7014:
7003:Ketan Mulmuley
6995:
6970:
6959:Seinosuke Toda
6951:
6949:; pp. 141–142
6919:
6912:
6877:
6860:
6856:
6852:
6848:
6822:
6807:
6783:
6753:
6726:
6699:
6669:
6657:Addison-Wesley
6638:
6637:
6635:
6632:
6628:Scott Aaronson
6623:
6620:
6619:
6618:
6604:
6600:
6579:
6559:
6537:
6533:
6512:
6492:
6472:
6451:
6448:
6427:
6416:
6402:
6398:
6375:
6371:
6350:
6330:
6310:
6286:
6266:
6242:
6239:
6216:
6212:
6191:
6188:
6168:
6165:
6143:
6139:
6118:
6115:
6110:
6106:
6102:
6099:
6090:with a weight
6079:
6070:be an edge in
6059:
6056:
6053:
6050:
6047:
6044:
6041:
6021:
5996:
5992:
5971:
5951:
5931:
5911:
5907:
5904:
5900:
5880:
5876:
5873:
5869:
5866:
5863:
5860:
5857:
5854:
5851:
5848:
5845:
5824:
5821:
5800:
5780:
5757:
5754:
5741:
5738:
5735:
5715:
5694:
5691:
5679:
5678:
5665:
5662:
5641:
5621:
5601:
5581:
5561:
5541:
5521:
5501:
5480:
5477:
5456:
5436:
5425:
5412:
5409:
5388:
5368:
5348:
5324:
5304:
5280:
5277:
5256:
5235:
5232:
5208:
5205:
5185:
5174:
5173:
5162:
5159:
5156:
5153:
5150:
5147:
5142:
5138:
5134:
5131:
5128:
5123:
5119:
5115:
5110:
5106:
5102:
5099:
5075:
5071:
5066:
5062:
5059:
5056:
5049:
5045:
5040:
5036:
5029:
5025:
5020:
5016:
5013:
4990:
4970:
4950:
4930:
4910:
4896:
4895:
4882:
4878:
4874:
4869:
4865:
4861:
4856:
4852:
4848:
4845:
4818:
4815:
4803:
4800:
4797:
4794:
4791:
4788:
4785:
4782:
4779:
4759:
4755:
4751:
4748:
4745:
4725:
4722:
4719:
4714:
4710:
4706:
4703:
4700:
4689:
4688:
4677:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4650:
4647:
4643:
4640:
4636:
4633:
4630:
4616:
4615:
4604:
4599:
4593:
4590:
4588:
4585:
4584:
4581:
4578:
4576:
4573:
4572:
4570:
4565:
4562:
4557:
4553:
4549:
4546:
4542:
4539:
4515:
4512:
4509:
4489:
4486:
4481:
4477:
4456:
4453:
4450:
4430:
4427:
4424:
4413:
4412:
4401:
4398:
4395:
4392:
4389:
4386:
4383:
4380:
4377:
4374:
4371:
4368:
4365:
4362:
4359:
4356:
4353:
4350:
4347:
4344:
4341:
4331:
4318:
4312:
4309:
4307:
4304:
4301:
4300:
4297:
4294:
4291:
4289:
4286:
4285:
4283:
4278:
4275:
4250:
4247:
4244:
4241:
4238:
4218:
4198:
4178:
4175:
4172:
4169:
4166:
4146:
4125:
4122:
4101:
4090:
4089:
4078:
4075:
4072:
4069:
4066:
4063:
4060:
4057:
4054:
4026:
4022:
4018:
4015:
4012:
4001:
3988:
3984:
3980:
3976:
3973:
3969:
3966:
3963:
3960:
3957:
3946:
3935:
3928:
3923:
3920:
3916:
3913:
3901:
3888:
3884:
3880:
3877:
3874:
3871:
3867:
3863:
3860:
3857:
3854:
3851:
3847:
3826:
3806:
3803:
3798:
3794:
3790:
3787:
3784:
3781:
3778:
3775:
3772:
3748:
3728:
3725:
3722:
3702:
3690:, as follows:
3678:
3675:
3654:
3633:
3630:
3609:
3593:
3590:
3584:
3581:
3568:
3563:
3559:
3555:
3552:
3549:
3529:
3526:
3523:
3520:
3517:
3512:
3508:
3504:
3501:
3496:
3492:
3488:
3485:
3482:
3460:
3456:
3432:
3429:
3426:
3423:
3420:
3417:
3414:
3411:
3408:
3405:
3402:
3399:
3375:
3353:
3349:
3326:
3322:
3301:
3281:
3259:
3255:
3234:
3212:
3208:
3185:
3181:
3160:
3140:
3120:
3100:
3080:
3058:
3054:
3031:
3027:
3001:
2997:
2974:
2970:
2947:
2943:
2922:
2900:
2896:
2875:
2872:
2869:
2849:
2829:
2809:
2789:
2767:
2763:
2742:
2720:
2716:
2703:
2700:
2687:
2667:
2645:
2641:
2620:
2598:
2594:
2573:
2551:
2547:
2526:
2506:
2486:
2466:
2446:
2426:
2406:
2384:
2380:
2357:
2353:
2332:
2309:
2289:
2269:
2249:
2229:
2209:
2189:
2167:
2163:
2140:
2136:
2113:
2109:
2086:
2082:
2061:
2041:
2021:
1999:
1995:
1974:
1954:
1932:
1928:
1915:
1912:
1898:
1894:
1890:
1867:
1863:
1848:internal edges
1844:external edges
1829:
1825:
1802:
1798:
1775:
1771:
1748:
1744:
1721:
1717:
1694:
1690:
1667:
1663:
1642:
1620:
1616:
1593:
1589:
1568:
1546:
1542:
1519:
1515:
1492:
1488:
1465:
1461:
1438:
1434:
1413:
1391:
1387:
1361:
1357:
1336:
1316:
1313:
1310:
1288:
1284:
1263:
1260:
1257:
1235:
1231:
1208:
1204:
1181:
1177:
1154:
1150:
1129:
1109:
1089:
1069:
1047:
1043:
1020:
1016:
988:
968:
948:
945:
942:
939:
919:
916:
913:
910:
907:
902:
899:
896:
893:
889:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
815:
812:
809:
806:
803:
798:
794:
773:
753:
750:
747:
744:
733:
732:
718:
714:
702:
688:
684:
661:
657:
636:
610:
606:
585:
565:
545:
533:
530:
529:
528:
525:
513:
491:
487:
464:
460:
439:
405:Cook's theorem
370:
350:
330:
308:
305:
301:
289:directed graph
272:
267:
264:
260:
256:
253:
250:
238:
235:
222:
219:
204:Ketan Mulmuley
185:Toda's theorem
151:Specifically,
127:
124:
75:Leslie Valiant
26:
9:
6:
4:
3:
2:
7099:
7088:
7085:
7083:
7082:Combinatorics
7080:
7078:
7075:
7074:
7072:
7060:
7056:
7051:
7040:
7039:
7034:
7027:
7018:
7011:
7008:
7004:
6999:
6985:on 2014-01-08
6984:
6980:
6974:
6967:
6964:
6960:
6955:
6948:
6944:
6940:
6937:
6936:
6931:
6926:
6924:
6915:
6913:0-262-03293-7
6909:
6905:
6904:
6899:
6895:
6891:
6887:
6881:
6874:
6858:
6854:
6850:
6846:
6835:
6831:
6826:
6818:
6814:
6810:
6804:
6801:. p. 2.
6800:
6796:
6795:
6787:
6780:
6776:
6772:
6768:
6767:
6762:
6761:Lance Fortnow
6757:
6749:
6745:
6741:
6737:
6730:
6723:
6719:
6715:
6711:
6710:
6703:
6696:
6692:
6688:
6687:Marcel Dekker
6685:
6683:
6678:
6673:
6666:
6665:0-201-53082-1
6662:
6658:
6655:
6651:
6646:
6644:
6639:
6631:
6629:
6602:
6598:
6577:
6557:
6535:
6531:
6510:
6490:
6470:
6449:
6446:
6425:
6417:
6400:
6396:
6373:
6369:
6348:
6328:
6308:
6300:
6299:
6298:
6284:
6264:
6255:
6240:
6237:
6214:
6210:
6189:
6186:
6166:
6163:
6141:
6137:
6116:
6113:
6108:
6104:
6100:
6097:
6077:
6054:
6051:
6048:
6042:
6039:
6019:
6010:
5994:
5990:
5969:
5949:
5929:
5905:
5902:
5874:
5871:
5864:
5861:
5858:
5852:
5846:
5843:
5822:
5819:
5798:
5778:
5769:
5762:
5753:
5739:
5736:
5733:
5713:
5692:
5689:
5663:
5660:
5639:
5619:
5599:
5579:
5559:
5539:
5519:
5499:
5478:
5475:
5454:
5434:
5426:
5410:
5407:
5386:
5366:
5346:
5338:
5337:
5336:
5322:
5302:
5293:
5278:
5275:
5254:
5233:
5230:
5220:
5206:
5203:
5183:
5157:
5151:
5148:
5145:
5140:
5136:
5132:
5129:
5126:
5121:
5117:
5113:
5108:
5104:
5100:
5097:
5073:
5069:
5064:
5060:
5057:
5054:
5047:
5043:
5038:
5034:
5027:
5023:
5018:
5014:
5011:
5004:
5003:
5002:
4988:
4968:
4961:. Every edge
4948:
4928:
4908:
4899:
4880:
4876:
4872:
4867:
4863:
4859:
4854:
4850:
4846:
4843:
4836:
4835:
4834:
4832:
4823:
4814:
4801:
4798:
4795:
4792:
4786:
4780:
4777:
4757:
4753:
4749:
4746:
4743:
4723:
4720:
4717:
4712:
4704:
4701:
4698:
4675:
4672:
4669:
4666:
4663:
4660:
4657:
4654:
4651:
4648:
4641:
4638:
4631:
4628:
4621:
4620:
4619:
4602:
4597:
4591:
4586:
4579:
4574:
4568:
4563:
4560:
4555:
4547:
4544:
4540:
4537:
4529:
4528:
4527:
4513:
4510:
4507:
4487:
4484:
4479:
4475:
4454:
4451:
4448:
4428:
4425:
4422:
4399:
4396:
4390:
4387:
4381:
4375:
4372:
4366:
4363:
4360:
4357:
4354:
4348:
4342:
4339:
4332:
4316:
4310:
4305:
4302:
4295:
4292:
4287:
4281:
4276:
4273:
4266:
4265:
4264:
4261:
4245:
4239:
4236:
4216:
4196:
4173:
4167:
4164:
4144:
4123:
4120:
4099:
4076:
4073:
4070:
4067:
4061:
4055:
4052:
4044:
4040:
4024:
4020:
4016:
4013:
4010:
4002:
3986:
3974:
3971:
3964:
3961:
3958:
3955:
3947:
3933:
3921:
3918:
3914:
3911:
3902:
3886:
3882:
3878:
3875:
3872:
3869:
3858:
3852:
3849:
3824:
3804:
3801:
3796:
3792:
3788:
3785:
3782:
3779:
3776:
3773:
3770:
3762:
3761:
3760:
3746:
3726:
3723:
3720:
3700:
3691:
3676:
3673:
3652:
3631:
3628:
3607:
3599:
3589:
3580:
3561:
3557:
3550:
3547:
3524:
3515:
3510:
3506:
3502:
3494:
3490:
3483:
3480:
3458:
3454:
3444:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3406:
3403:
3400:
3387:
3373:
3351:
3347:
3324:
3320:
3299:
3279:
3257:
3253:
3232:
3210:
3206:
3183:
3179:
3158:
3138:
3118:
3098:
3078:
3056:
3052:
3029:
3025:
3015:
2999:
2995:
2972:
2968:
2945:
2941:
2920:
2898:
2894:
2873:
2870:
2867:
2847:
2827:
2807:
2787:
2765:
2761:
2740:
2718:
2714:
2699:
2685:
2665:
2643:
2639:
2618:
2596:
2592:
2571:
2549:
2545:
2524:
2504:
2484:
2464:
2444:
2424:
2404:
2382:
2378:
2355:
2351:
2330:
2321:
2307:
2287:
2267:
2247:
2227:
2207:
2187:
2165:
2161:
2138:
2134:
2111:
2107:
2084:
2080:
2059:
2052:just in case
2039:
2019:
1997:
1993:
1972:
1952:
1930:
1926:
1911:
1892:
1865:
1861:
1851:
1849:
1845:
1827:
1823:
1800:
1796:
1773:
1769:
1746:
1742:
1719:
1715:
1692:
1688:
1665:
1661:
1640:
1618:
1614:
1591:
1587:
1566:
1544:
1540:
1517:
1513:
1490:
1486:
1463:
1459:
1436:
1432:
1411:
1389:
1385:
1375:
1359:
1355:
1334:
1314:
1311:
1308:
1286:
1282:
1261:
1258:
1255:
1233:
1229:
1206:
1202:
1179:
1175:
1152:
1148:
1127:
1107:
1087:
1080:variables in
1067:
1045:
1041:
1018:
1014:
1004:
1000:
986:
966:
943:
937:
914:
905:
897:
891:
887:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
810:
801:
796:
792:
771:
748:
716:
712:
703:
686:
682:
659:
655:
634:
626:
625:
624:
608:
604:
583:
563:
543:
526:
511:
489:
485:
462:
458:
437:
429:
428:
427:
425:
420:
418:
414:
410:
406:
402:
398:
394:
390:
386:
384:
368:
348:
328:
306:
303:
299:
290:
286:
265:
262:
258:
251:
248:
234:
232:
228:
218:
216:
211:
210:of a matrix.
209:
205:
201:
197:
192:
190:
186:
182:
178:
174:
170:
166:
162:
158:
154:
148:
146:
142:
136:
134:
123:
121:
117:
113:
110:
105:
103:
99:
94:
92:
88:
84:
80:
76:
72:
68:
64:
60:
56:
52:
48:
41:
37:
33:
19:
7050:
7037:
7032:
7026:
7017:
6998:
6987:. Retrieved
6983:the original
6973:
6954:
6934:
6930:Dexter Kozen
6902:
6880:
6837:
6825:
6793:
6786:
6765:
6756:
6739:
6735:
6729:
6708:
6702:
6681:
6672:
6653:
6625:
6256:
6011:
5770:
5767:
5680:
5294:
5221:
5175:
4981:with weight
4900:
4897:
4828:
4690:
4617:
4414:
4262:
4091:
4045:. Otherwise
4042:
4038:
3692:
3595:
3586:
3445:
3388:
3016:
2705:
2631:have weight
2322:
1917:
1852:
1847:
1843:
1532:appears. If
1376:
1005:
1001:
734:
576:clauses and
535:
421:
387:
240:
224:
212:
193:
168:
164:
150:
140:
138:
132:
129:
126:Significance
106:
95:
69:. In a 1979
50:
46:
44:
31:
7055:S. Aaronson
6321:from graph
5339:If an edge
2678:has weight
2240:. The term
1120:clauses in
1006:To specify
701: ; and
417:#P-complete
401:#P-complete
227:#P-complete
208:determinant
181:#P-complete
87:#P-complete
7071:Categories
6989:2016-07-06
6817:0948.68082
6677:Allen Kent
6667:. Page 443
6634:References
6341:is not in
6179:nodes and
5359:is not in
5196:nodes and
4037:then Perm(
623:such that
341:to vertex
91:#P problem
57:about the
38:is due to
5865:
5847:
5737:
5152:
5146:≤
5133:≤
5130:⋯
5127:≤
5114:≤
5101:≤
5058:⋯
4781:
4667:⋅
4655:⋅
4632:
4476:μ
4449:μ
4388:−
4382:⋅
4373:−
4361:⋅
4343:
4303:−
4293:−
4246:μ
4240:
4174:μ
4168:
4074:−
4056:
3965:
3883:μ
3879:⋅
3870:≤
3853:
3793:μ
3789:⋅
3780:⋅
3747:μ
3724:×
3583:01-Matrix
3562:ϕ
3551:
3525:ϕ
3522:#
3516:⋅
3495:ϕ
3484:
3401:−
3030:ϕ
2973:ϕ
2899:ϕ
2871:∪
2766:ϕ
2572:ϕ
2505:ϕ
2208:ϕ
2040:ϕ
1998:ϕ
1953:ϕ
1931:ϕ
1893:ϕ
1866:ϕ
1653:in which
1641:ϕ
1567:ϕ
1437:ϕ
1412:ϕ
1360:ϕ
1301:for some
1248:for some
1180:ϕ
1128:ϕ
1088:ϕ
1046:ϕ
1019:ϕ
967:ϕ
944:ϕ
915:ϕ
912:#
906:⋅
898:ϕ
837:−
811:ϕ
808:#
802:⋅
772:ϕ
749:ϕ
746:#
717:ϕ
660:ϕ
635:ϕ
609:ϕ
544:ϕ
512:ϕ
490:ϕ
463:ϕ
438:ϕ
419:as well.
59:permanent
6781:; p. 265
6724:; p. 90.
6689:, 1999.
6659:, 1994.
6450:′
6241:′
5906:′
5875:′
5823:′
5693:′
5664:′
5532:, where
5479:′
5411:′
5279:′
5234:′
4642:′
4541:′
4124:′
3975:′
3948:Compute
3915:′
3903:Compute
3763:Compute
3677:′
3632:′
3366:will be
3225:, where
735:Thus if
237:Overview
63:matrices
6697:; p. 34
5219:edges.
4736:. Then
4526:. Thus
2457:, then
424:#P-hard
291:, with
83:#P-hard
53:, is a
6945:
6910:
6815:
6805:
6777:
6720:
6693:
6663:
5677:match.
5447:is in
5424:match.
4467:, and
4415:Here,
3713:be an
3596:Using
2840:is an
2800:. Let
930:where
202:) and
7042:(PDF)
5791:be a
4921:be a
4770:, so
4500:, so
4112:into
556:with
287:of a
100:as a
6943:ISBN
6908:ISBN
6803:ISBN
6775:ISBN
6718:ISBN
6691:ISBN
6661:ISBN
6114:>
5942:and
5862:Perm
5844:Perm
5771:Let
5726:and
5652:and
5552:and
5399:and
5267:and
4901:Let
4778:Perm
4747:<
4629:Perm
4340:Perm
4229:and
4157:and
4053:Perm
4041:) =
4014:<
3962:Perm
3850:Perm
3693:Let
3548:Perm
3481:Perm
1312:>
1259:<
979:" –
391:, a
389:#SAT
45:The
6838:An
6813:Zbl
6744:doi
6570:to
6483:to
6277:in
5982:is
5734:log
5512:to
5427:If
5315:in
5149:log
4709:mod
4705:227
4691:so
4676:227
4552:mod
4237:log
4165:log
4003:If
3983:mod
3927:mod
2987:by
2564:in
1985:of
1404:of
1167:in
999:.)
413:CNF
61:of
7073::
7057:,
7033:#P
7005:.
6961:.
6932:.
6922:^
6896:;
6892:;
6888:;
6836::
6832:,
6811:.
6763:.
6738:.
6652:.
6642:^
6297:.
6009:.
5752:.
5335:.
5292:.
5090:,
4844:13
4802:6.
4670:15
4664:15
4587:15
4580:15
4514:17
4441:,
4400:6.
3759:.
3507:12
3455:12
3386:.
3254:12
3014:.
2640:12
793:12
683:12
385:.
233:.
196:NC
191:.
135::
104:.
98:#P
73:,
6992:.
6916:.
6859:2
6855:/
6851:5
6847:n
6819:.
6750:.
6746::
6740:8
6684:.
6603:r
6599:2
6578:v
6558:u
6536:r
6532:2
6511:r
6491:v
6471:u
6447:G
6426:G
6401:e
6397:J
6374:e
6370:J
6349:R
6329:G
6309:e
6285:G
6265:R
6238:G
6215:e
6211:J
6190:r
6187:6
6167:r
6164:2
6142:e
6138:J
6117:1
6109:r
6105:2
6101:=
6098:w
6078:G
6058:)
6055:v
6052:,
6049:u
6046:(
6043:=
6040:e
6020:G
5995:p
5991:2
5970:G
5950:p
5930:n
5910:)
5903:G
5899:(
5879:)
5872:G
5868:(
5859:=
5856:)
5853:G
5850:(
5820:G
5799:n
5779:G
5740:W
5714:n
5690:G
5661:G
5640:G
5620:G
5600:r
5580:e
5560:v
5540:u
5520:v
5500:u
5476:G
5455:R
5435:e
5408:R
5387:R
5367:R
5347:e
5323:G
5303:R
5276:G
5255:G
5231:G
5207:r
5204:3
5184:r
5161:)
5158:w
5155:(
5141:r
5137:x
5122:2
5118:x
5109:1
5105:x
5098:0
5074:r
5070:x
5065:2
5061:+
5055:+
5048:2
5044:x
5039:2
5035:+
5028:1
5024:x
5019:2
5015:=
5012:w
4989:w
4969:e
4949:W
4929:n
4909:G
4881:0
4877:2
4873:+
4868:2
4864:2
4860:+
4855:3
4851:2
4847:=
4799:=
4796:P
4793:=
4790:)
4787:A
4784:(
4758:2
4754:/
4750:Q
4744:P
4724:6
4721:=
4718:7
4713:1
4702:=
4699:P
4673:=
4661:+
4658:1
4652:2
4649:=
4646:)
4639:A
4635:(
4603:.
4598:]
4592:1
4575:2
4569:[
4564:=
4561:7
4556:1
4548:A
4545:=
4538:A
4511:=
4508:Q
4488:4
4485:=
4480:n
4455:2
4452:=
4429:2
4426:=
4423:n
4397:=
4394:)
4391:2
4385:(
4379:)
4376:2
4370:(
4367:+
4364:1
4358:2
4355:=
4352:)
4349:A
4346:(
4317:]
4311:1
4306:2
4296:2
4288:2
4282:[
4277:=
4274:A
4249:)
4243:(
4217:n
4197:Q
4177:)
4171:(
4145:n
4121:A
4100:A
4077:Q
4071:P
4068:=
4065:)
4062:A
4059:(
4043:P
4039:A
4025:2
4021:/
4017:Q
4011:P
3987:Q
3979:)
3972:A
3968:(
3959:=
3956:P
3934:Q
3922:A
3919:=
3912:A
3887:n
3876:!
3873:n
3866:|
3862:)
3859:A
3856:(
3846:|
3825:Q
3805:1
3802:+
3797:n
3786:!
3783:n
3777:2
3774:=
3771:Q
3727:n
3721:n
3701:A
3674:A
3653:A
3629:A
3608:A
3567:)
3558:G
3554:(
3528:)
3519:(
3511:m
3503:=
3500:)
3491:G
3487:(
3459:m
3431:}
3428:3
3425:,
3422:2
3419:,
3416:1
3413:,
3410:0
3407:,
3404:1
3398:{
3374:0
3352:M
3348:Z
3325:j
3321:C
3300:M
3280:M
3258:m
3233:M
3211:M
3207:Z
3184:M
3180:Z
3159:L
3139:m
3119:M
3099:M
3079:M
3057:M
3053:Z
3026:G
3000:M
2996:Z
2969:G
2946:M
2942:L
2921:M
2895:G
2874:L
2868:M
2848:M
2828:L
2808:M
2788:M
2762:G
2741:Z
2719:j
2715:C
2686:0
2666:Z
2644:m
2619:Z
2597:i
2593:x
2550:i
2546:x
2525:Z
2485:Z
2465:Z
2445:Z
2425:Z
2405:Z
2383:j
2379:C
2356:j
2352:C
2331:Z
2308:M
2288:M
2268:M
2248:Z
2228:Z
2188:Z
2166:i
2162:x
2139:i
2135:x
2112:i
2108:x
2085:i
2081:x
2060:Z
2020:Z
1994:G
1973:Z
1927:G
1897:|
1889:|
1862:G
1828:i
1824:x
1801:i
1797:x
1774:i
1770:x
1747:i
1743:x
1720:i
1716:x
1693:j
1689:C
1666:i
1662:x
1619:j
1615:C
1592:j
1588:C
1545:i
1541:x
1518:i
1514:x
1491:j
1487:C
1464:i
1460:x
1433:G
1390:i
1386:x
1356:G
1335:j
1315:j
1309:o
1287:i
1283:C
1262:j
1256:i
1234:i
1230:C
1207:j
1203:C
1176:G
1153:j
1149:C
1108:m
1068:n
1042:G
1015:G
987:m
947:)
941:(
938:t
918:)
909:(
901:)
895:(
892:t
888:4
867:}
864:3
861:,
858:2
855:,
852:1
849:,
846:0
843:,
840:1
834:{
814:)
805:(
797:m
752:)
743:(
713:G
687:m
656:G
605:G
584:n
564:m
486:G
459:G
369:A
349:j
329:i
307:j
304:i
300:a
271:)
266:j
263:i
259:a
255:(
252:=
249:A
169:n
165:n
42:.
36:#
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.