# Why do Integer Relation Algorithms (e.g. PSLQ) not solve the knapsack problem?

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?

-
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