22
$\begingroup$

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$.

We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)\times (1+\exp(iA_1t))\times\cdots\times(1+\exp(iA_nt)) \, dt.$$

The question then becomes what $I=0$ or $I\geq 1$.

Can we not approach the value of $I$ with the method of Monte Carlo, or others?

Why are these approaches not succeeding?

Remark : it's not difficult to find a good approximation of $B\times t \bmod 2\pi$, where $B$ is a big integer and $t\in [0,2\pi]$, because we know excellent approximation of $\pi$.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ 'We know excellent approximation[s] of $\pi$' doesn't matter in the asymptotic limit; we can't assume that we have 'all of' $\pi$ written down in advance so computing it has to be part of the calculation as well. $\endgroup$
    – Steven Stadnicki
    Commented Apr 13, 2022 at 1:31
  • 1
    $\begingroup$ @StevenStadnicki true, but the computation of pi isn’t going to be the bottleneck here, see for example this paper. (Related discussion here.) $\endgroup$
    – Dan Romik
    Commented Apr 13, 2022 at 1:37
  • 2
    $\begingroup$ @DanRomik That depends entirely on how many digits we need. Since as Noam Elkies's answer notes we have waves of frequency $A_i=\theta(2^n)$, then to compute $A_it\bmod \pi$ we still need (as far as we know) $\theta(2^n)$ digits — i.e. exponentially many. $\endgroup$
    – Steven Stadnicki
    Commented Apr 13, 2022 at 1:41
  • 2
    $\begingroup$ @StevenStadnicki okay, I suppose that's true. In that case I'll revise the point that I was trying to make earlier about bottlenecks: the point is that even if we were allowed to use an oracle that computes $\pi$ at any desired precision for zero computational cost, it likely wouldn't be of much help in computing the integral in polynomial time. (Not that I have an idea how to prove such a statement; I'm just speaking heuristically here.) So in that sense, I'm guessing that $\pi$ is not the bottleneck. $\endgroup$
    – Dan Romik
    Commented Apr 13, 2022 at 7:21
  • $\begingroup$ Anyone here with a copy of Mathematica who can create a graph for the function, say if Ak = nth prime. and V is half their total size, rounded to an even integer? I suspect you run into trouble for relatively small an, while solving it for say n = 1,000,000 is no big deal with a pseudo-polynomial algorithm. $\endgroup$
    – gnasher729
    Commented Apr 13, 2022 at 17:12

2 Answers 2

Reset to default
51
$\begingroup$

The size of the problem is measured by the number of digits it takes to specify $V$ and $A_1,\ldots,A_n$. If each is less then $n$ bits then the input size is $< n^2$ but each of the factors $(1 + \exp(i A_k t))$ oscillates an exponential number of times (almost $2^n$) in $[0,2\pi]$. We don't know how to tell in polynomial time whether such an integral is zero or $\geq 1$.

Improve this answer
$\endgroup$
6
  • 6
    $\begingroup$ For instance (to use OP's suggestion), to get sufficient resolution for Monte Carlo integration to return a 'trustable' value we would have to sample roughly $\Omega(\sum_i 2^{A_i})$ points because of the Nyquist sampling theorem. $\endgroup$
    – Steven Stadnicki
    Commented Apr 13, 2022 at 1:37
  • 16
    $\begingroup$ This is good as a heuristic explanation of why OP’s approach isn’t likely to work. But perhaps we should make clear that there’s no a priori guarantee that someone couldn’t find some ingenious way of approximating the integral in polynomial time. In other words, this approach is no less viable as a way of proving P=NP (for someone who believes that’s not an utter waste of time) than the more direct combinatorial approach, for which there is an equally convincing heuristic explanation of why it’s unlikely to work. $\endgroup$
    – Dan Romik
    Commented Apr 13, 2022 at 2:13
  • 4
    $\begingroup$ @StevenStadnicki There may be another good point in there. Having only a trustable answer may not good enough. To show that P=NP you need a polynomial time algorithm that always works, not one that works 99,99999% of the time. The latter would only show NP $\subset$ BPP (which would be a big result in itself though). $\endgroup$
    – mlk
    Commented Apr 13, 2022 at 8:42
  • $\begingroup$ @DanRomik, in principle yes. But OP is asking why his approach does not just "simply" solve P=?=NP once and for all, assuming/implying his approach is solvable polynomial time, even if only as an approximation. This answer shows - on an equally rough level of detail to the answer - the "exponentiality" aspect contained in OP's algorithm. Seems a pretty OK answer to me. At this point, one would have to come up with a way to make OP's algo polynomial with the added info from this answer; that the answer has details left open seems inconsequential to me. $\endgroup$
    – AnoE
    Commented Apr 13, 2022 at 13:22
  • 2
    $\begingroup$ @AnoE sure, it’s a good answer and I upvoted it. I just thought we should be clear about the limits of our knowledge, so that people who might be inclined to think about this integral approach further don’t assume at the outset the idea is completely impossible and get scared away. Call it “informed consent”. Even if the approach doesn’t lead to a proof that P=NP (it most probably won’t) there may well be some useful insights to be gained from thinking about it. $\endgroup$
    – Dan Romik
    Commented Apr 13, 2022 at 14:32
21
$\begingroup$

So you managed to reduce an NP complete problem to calculating a single integral. Actually, in the original Garey / Johnson book, one of their 320 NP complete problems is exactly what we have here (verifying whether some integral has a value of 0; their integral can actually be solved in closed form, but to do that you have to do a lot of steps where each step makes the problem simpler but increases its size - so you end up with something that is just too big to handle in less than exponential time. And numerical calculation also fails).

The problem is that your integral cannot be solved in closed form as far as I can tell, but it is also the integral of a function that changes incredibly much. Numerical integration has no chance to solve the integral with the required precision in any reasonable amount of time, and Monte Carlo approximations have no chance - they can give reasonable approximations to some class of integrals, but their precision is even lower than numerical integration.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .