×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), 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 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, ()
[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, () · 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, (), TR75-224
[20] Simon, J., On the difference between one and many, 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. (to appear). · 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, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.