[seqfan] Re: easy and bref
franktaw at netscape.net
franktaw at netscape.net
Fri Sep 30 19:36:48 CEST 2011
All right, that's a good question. I seem to remember seeing some, but
I can't find any right now.
I guess in practice I don't apply this quite the way I stated it here.
If a problem is well studied, and no efficient algorithm has been
found, then the "hard" keyword applies. So it is appropriate for the
Mersenne primes.
Where I object to its use is the case where someone basically says, "I
don't know how to calculate this, so we'll call it hard." There should
be at least some theory suggesting that it really is hard.
Franklin T. Adams-Watters
-----Original Message-----
From: Charles Greathouse <charles.greathouse at case.edu>
That's a non-example; I can think of many. But what would an example
be?
Charles Greathouse
Analyst/Programmer
Case Western Reserve University
On Fri, Sep 30, 2011 at 1:07 PM, <franktaw at netscape.net> wrote:
> Well, consider A000043: Mersenne primes (p with 2^p-1 prime).
>
> Currently, we don't know any very efficient way of calculating these.
> (Better than primality testing for other numbers of the magnitude
2^p, but
> still very expensive as a function of p.) However, no one has proved
that
> there isn't an efficient way to compute these. (The list might even be
> finite, in which case there is a very efficient calculation.)
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Charles Greathouse <charles.greathouse at case.edu>
>
>> Interesting. My understanding of "hard" was just the opposite: that
it
>> should be used when it is known that calculating more terms is hard,
>
> but not
>>
>> when there might be an easier way to make the calculation, but none
>
> such is
>>
>> known.
>
> I'm not sure when that would ever apply. Would you give some
examples?
>
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
_______________________________________________
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list