×

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


MSC:

68Q25 Analysis of algorithms and problem complexity
15A15 Determinants, permanents, traces, other special matrix functions
PDFBibTeX XMLCite
Full Text: DOI

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)
[4] Gill, J., Computational complexity of probabilistic Turing machines, Proc. 6th ACM Symp. on Theory of Computing, 91-95 (1974)
[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.