Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such.

The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to $A$?) is NP-complete. However, integer relations (given the same $a_i$, are there integer $c_i$ below a fixed but arbitrarily large bound such that $\Sigma c_i a_i = A$?) can be solved, both as decisional problem and as answer-finding problem, efficiently (in polynomial time in the size of the inputs), e.g. by PSLQ.

This seems to be a contradiction to me: If the subset sum problem has a solution, PSLQ should find it in polynomial time. And if it does not, PSLQ should report this in polynomial time. But if that were true, the subset sum problem would be solvable in polynomial time and hence would be in P.

So what am I missing?

share|improve this question

2 Answers 2

The problem you've described is usually known as subset sum, which can be thought of as a special case of the knapsack problem where the weights and values are equal for each item and the weight and value limits are also the same.

PSLQ cannot solve these problems in polynomial time because the arithmetic operations that it performs (repeatedly squaring and dividing the terms) cause an exponential blowup in the size of the inputs. Unfortunately, exponentially sized data requires exponential time to store and manipulate, otherwise NP-complete problems would indeed be decidable in polynomial time.

share|improve this answer
    
+1 (if only I could...) for "subset sum" (I guess I should update the question...!) and the real computation link! –  pyramids Oct 31 '13 at 21:07
    
How can I see that exponential space is required? Naively, it would seem that if $n$ bits are needed for each of $m$ input coefficients $a_i$, then $O(1) \cdot m \cdot a_i$ should typically suffice for the integer relation algorithm to be able to distinguish between the case of an actual solution with $\Sigma |c_i| \le m$ and the case that no such solutions exist. –  pyramids Oct 31 '13 at 21:12
    
I suspect this answer is correct, but it is hard for me to see just why/how the required precision increases quite so strongly. That is why I have not accepted it as correct answer yet. –  pyramids Apr 24 at 11:09

The subset sum problem is NP-complete: http://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_problem Hence it is very unlikely (unless one believes in P=NP) that there is a polynomial algorithm for it.

The integer relation problem is different as the integers there may have arbitrary sign and be arbitrarily large, whereas the integers in the subset sum problem are constrained to be 0 or 1.

The integer relation problem can be solved in polynomial time (without bounds on the integers) by a modified LLL algorithm: M Pohst, A modification of the LLL reduction algorithm \url{https://jogins.com/media/Mathematics/Mathematics 2/Number theory/Algorithmic Methods In Algebra And Number Theory - Pohst M.pdf}

share|improve this answer
    
I agree with everything you say, but I fail to see the relevancy. If there is a solution with coefficients constrained to 0 and 1, any algorithm solving the more general integer relation problem, be it LLL or something more advanced like PSLQ, will either find it or, in very rare cases, find (or get stuck on) additional solutions, and with typically(?) only slightly increased calculation accuracy, this complication will go away in almost all instances (albeit not in some pathological ones). So to me, your answer does sound like a re-statement of the paradox giving rise to my question. –  pyramids Apr 23 at 20:34
    
@pyramids: An algorithm for solving the integer constrained problem in polynomial time will just find some integer relation. This is very unlikely to be a (0,1) solution (which might not even exist). It cannot get stuck since it is not based on enumerating near solutions. –  Arnold Neumaier Apr 24 at 8:42
    
With (approximations to) irrational input numbers, in most cases, no solution will exist, and if it does, it is either spurious (for being too crude an approximation) or reducible to a solution with minimum integer numbers. So if the integer relation algorithm (where the output integers are indeed limited---it would be trivial to generate an arbitrarily large spurious solution) does return a relation, either there's a 0-1 solution or a larger/no solution that, at least for the PSLQ algorithm, does come with a bound for other possible solutions. –  pyramids Apr 24 at 11:08
    
@pyramids: 1000 x+ 1001 y = 1 has inifintely many integer solutions but no 0,1 solutions. But even if an equation has a 0,1 solution, why do you expect that an algorithm for finding one of the infinitely many integer solutions should always produce the 01 solution eceot in rare cases?? –  Arnold Neumaier Apr 24 at 13:34
    
PSLQ will not only always find a (in some sense small-ish) solution if there is one, but also give a lower bound for the norm of the smallest possible solution. My possibly wrong intuition stems from considering the input to be an approximation to numbers drawn from a continuum, e.g. 1001+sqrt(2) and 8007+8*sqrt(2), if you like. Hence I (wrongly?) assumed very small solutions to be relatively rare, and the typical outcome being either to find the 01 solution or such a large solution that the associated lower bound for the norm of any solution excludes the existence of a 01 solution. –  pyramids Apr 25 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.