×
Valiant, L. G.

The complexity of computing the permanent. (English) Zbl 0415.68008

Theor. Comput. Sci. 8, 189-201 (1979).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0415.68008

Cited in 18 Reviews
Cited in 750 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
15A15 Determinants, permanents, traces, other special matrix functions

Keywords:

computational complexity; permanent of a matrix; determinant
Cite Review PDF
Full Text: DOI

Online Encyclopedia of Integer Sequences:

a(n) = number of different ways to seat a set of n married male-female couples at a round table so that men and women alternate and every man is separated by at least d = 2 men from his wife.

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0207.01701
[2] Bauer, M.; Brand, D.; Fischer, M.; Meyer, A.; Paterson, M., A note on disjunctive form tautologies, SIGACT News, 52, 17-20 (1973)
[3] Cook, S. A., The complexity of theorem proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 151-158 (1971) · Zbl 0253.68020
[4] Gill, J., Computational complexity of probabilistic Turing machines, Proc. 6th ACM Symp. on Theory of Computing, 91-95 (1974) · Zbl 0357.68056
[5] Hall, M., An algorithm for distinct representatives, Am. Math. Monthly, 63, 716-717 (1956) · Zbl 0074.25004
[6] Harary, F.; Palmer, E. M., Graphical Enumeration (1973), Academic Press: Academic Press New York · Zbl 0266.05108
[7] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1960), Oxford University Press · Zbl 0086.25803
[8] Hartmanis, J.; Berman, L., On Isomorphisms and density of NP and other complete sets, Proc. 8th ACM Symp. on Theory of Computing, 30-40 (1976) · Zbl 0365.68045
[9] Herrmann, P. P., On reducibility among combinatorial problems, (MAC TR-113 (1973), MIT)
[10] Hopcroft, J. E.; Karp, R. M., An \(n^{52}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114
[11] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York) · Zbl 0366.68041
[12] Little, C. H.C., A characterization of convertible (0, 1)-matrices, J. Combin. Theory, 18, B, 187-208 (1975) · Zbl 0281.05013
[13] Marcus, M.; Minc, H., On the relation between the determinant and the permanent, Illinois J. Math., 5, 376-381 (1961) · Zbl 0104.00904
[14] Meyer, A. R.; Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential space, Proc. 13th Symp. on Switching and Automata Theory, 125-129 (1972)
[15] Muir, T., On a class of permanent symmetric functions, Proc. Roy. Soc. Edinburgh, 11, 409-418 (1882) · JFM 15.0128.01
[16] Polya, G., Aufgabe 424, Arch. Math. Phys., 20, 3, 27 (1913)
[17] Ryser, H. J., Combinatorial Mathematics, Carus Math. Monograph no. 14 (1963) · Zbl 0112.24806
[18] Schnorr, C. P., A lower bound on the number of additions in monotone computations, Theor. Comput. Sci., 2, 305-315 (1976) · Zbl 0342.68024
[19] Simon, J., On some central problems in computational complexity, (Ph.D. Thesis (1975), Cornell Univ), TR75-224
[20] Simon, J., On the difference between one and many, Turku. Turku, Proc. 4th Colloq. on Automata, Languages and Programming (1977)
[21] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[22] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[23] Valiant, L. G., A polynomial reduction of satisfiability to Hamiltonian circuits that preserves the number of solutions (1974), Univ. of Leeds, Manuscript
[24] Valiant, L. G., The relative complexity of checking and evaluating, Information Processing Lett., 5, 1, 20-23 (1976) · Zbl 0342.68028
[25] L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput.; L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. · Zbl 0419.68082
[26] Diffie, W.; Hellman, M. E., New directions is cryptography, IEEE. Trans Information Theory (Nov. 1976), New York
[27] Pratt, V. R., Every prime has a succint certificate, SIAM J. Comput., 4, 214-220 (1975) · Zbl 0316.68031
[28] Rivest, R. L.; Shamir, A.; Adleman, L., On digital signatures and public-key cryptosystems, (TM 82 (April 1977), Lab. for Comput. Sci., MIT) · Zbl 0368.94005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.