I'm absolutely new to GPU programming so I apologize if my question is obvious.

Can GPU and AMD java library for GPU be used to solve Subset sum problem

http://en.wikipedia.org/wiki/Subset_sum_problem ?

Is this the type of task that might promise better results than few CPUs?

Thanks,

--MG

Yes.

Exponential time algorithm: Each work-item will correspond to the single combination (or a bunch of combinations in case the set is large). But there is memory limitation: you should be able to store 2*2^(N/2) elements in the device memory.

Pseudo-polynomial time dynamic programming solution: N+P (N is the sum of the negative values and

Pis the sum of the positive values) should be big enough (at least several hundreds) to efficiently utilize GPU. Each dynamic programming pass corresponds to single kernel run.