On Thu, 29 Sep 2011 19:45:48 +0100, Peter Percival <firstname.lastname@example.org> wrote:
> Given a finite set of numbers [...]
Thank you for all replies.
My (as opposed to the) problem with the two piles of books was actually a multiset problem rather than a set problem, but I forgot that when I "mathematicized" it. Never mind, it seems there is not much difference between the two.
So the problem is hard (in a sense that can be made precise, and that I still need to read up on); but is it unavoidably hard? By that I mean, is it just that no better-than-exponential-time algorithm has been found, or is it that there is none to be found? I am aware that there are problems that are intrinsically unsolvable (halting problem, for example), but are there any that are provably intrinsically difficult?