On Approximating Hard Integrals with the Double-Exponential Formula. Academic Article uri icon

abstract

  • The Partition Counting Problem (# PART) is the following: given n positive integers {xk} nk= 1, in how many ways is it possible to divide them into two equal-sum subsets. Analytic and number-theoretic approaches to this problem can be found in many works, many seem to go back to the classic monograph [1] by Kac. If the input {xk} is given in binary rather unary radix, then solving this problem in polynomial time wrt the input's length would prove P=# P and would also entail P= NP. Assuming the exponential time hypothesis,# PART cannot be solved in polynomial time.

publication date

  • December 1, 2015