Why do Integer Relation Algorithms (e.g. PSLQ) not solve the subset sum 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?
 A: 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.
A: 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}
