A note on the permanent value problem. (English) Zbl 0780.68067

Saluja, Sanjeev

Inf. Process. Lett. 43, No. 1, 1-5 (1992).

Summary: We show that computing the permanent of matrices over integers is hard for the class \(GapP\) under product reductions. Using this result, we show new decision problems complete for the counting classes \(PP\), \(C_ =P\).

MSC:

68Q25	Analysis of algorithms and problem complexity
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
15A15	Determinants, permanents, traces, other special matrix functions
15B36	Matrices of integers

Keywords:

integer matrices; computational complexity; permanent; counting classes

References:

[1]	Cook, S., The complexity of theorem proving procedures, Proc. 3rd ACM Symp. on Theory of Computing, 151-158 (1971) · Zbl 0253.68020
[2]	Fenner, S.; Fortnow, L.; Kurtz, S., Gap-definable counting classes, Proc. 6th Ann. Conf. on Structure in Complexity Theory, 30-42 (1991)
[3]	Gill, J., Computational complexity of probabilistic Turing machines, SIAM J. Comput, 6, 675-695 (1977) · Zbl 0366.02024
[4]	Savage, J. E., Computational work and time on finite machines, J. ACM, 19, 660-674 (1972) · Zbl 0251.68031
[5]	Simon, J., On some central problems in computational complexity, Ph.D. Thesis (1975), Dept. of Computer Science, Cornell University, Tech. Rept. TR75-224
[6]	Stockmeyer, L. J., The polynomial time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1976) · Zbl 0353.02024
[7]	Toda, S., PP is as hard as the polynomial-time hierarchy, SIAM J. Comput., 20, 5, 865-877 (1991) · Zbl 0733.68034
[8]	Valiant, L. G., The complexity of computing the permanent, Theoret. Comput. Sci., 8, 189-201 (1979) · Zbl 0415.68008
[9]	Wagner, K., the complexity of combinatorial problems with succint input representations, Acta Inform., 23, 325-326 (1986) · Zbl 0621.68032