| Definite integration and summation are P-hard (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| We show that the common symbolic manipulation tasks of computing multiple partial derivatives, definite integration, and definite summation, are #P-hard, i.e., at least as hard as counting the accepting input strings for any Turing machine that halts in polynomial time. Keywords --- multiple partial derivatives, definite integration, definite summation, symbolic manipulation tasks, #Pcompleteness, permanents, Ryser's formula. 1 Permanents, averaging, and partial differentiation L ET A be an n \Theta n matrix A = 0 B B @ a 11 a 12 : : : a 1n a 21 a 22 : : : a 2n . . . . . . . . . . . . an1 an2 : : : ann 1 C C A : (1) The "permanent" of A is defined by perA = X oe a 1;oe(1) a 2;oe(2) \Delta \Delta \Delta a n;oe(n) (2) where the sum is over the n! permutations oe of f1; 2; :::; ng. L.G.Valiant [7] showed that computing the permanent of a matrix whose elements lay in the set f\Gamma1; 0; 1; 2; 3g was #P-complete. We first note that perA = coeff: of z 1 z 2 \Delta \Delta \D... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||