Modular Arithmetic and Calculus Problems in #P
Ohad Asor · arXiv (Cornell University) · 2016
Given n integers x[1],...,x[n], it is obvious that calculating the n LSB bits of the integer part of prod(2^(n*x[k])+2^(-n*x[k])) has polynomial time complexity if the integers are supplied in unary radix. We show that if the input is supplied in binary (or higher) radix, then this problem is in #P and is actually the counting version of the Partition problem. We also state additional properties of the Partition problem following our analysis. In particular, we show that deciding whether definite integrals are zero or infinite is NP-Complete under some settings. We also show how to count all integer partitions that are divisible by a given factor, and how it is related to the Trapezoid rule from numerical analysis.