The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Seeking an algorithm
Replies: 22   Last Post: Oct 3, 2011 3:01 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Peter Percival

Posts: 2,623
Registered: 10/25/10
Re: Seeking an algorithm
Posted: Oct 1, 2011 8:27 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Thu, 29 Sep 2011 19:45:48 +0100, Peter Percival
<> 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?

Using Opera's revolutionary email client:

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.