Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


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

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: 1,370
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
<peterxpercival@hotmail.com> 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: http://www.opera.com/mail/



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.