[seqfan] Re: easy and bref
D. S. McNeil
dsm054 at gmail.com
Fri Sep 30 19:31:31 CEST 2011
> 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.)
How many "isn't an efficient way to compute these" proofs are there,
though? We can't even show P != NP..
I can imagine sequences I'd give "hard" to for which someone could
find a generating function at which point it'd be easy. Counting
graphs with certain properties, for example. So anything which
_could_ have a generating function or formula can't have the keyword
hard?
I guess I don't see "hard" as a permanent property but as a
description of our state of knowledge. Right now, A060843 -- the busy
beaver problem -- only has four known terms, and not for lack of
interest. Why only four? Because the sequence is hard in the
colloquial sense. If someone comes up with a formula and we suddenly
had lots of terms, we'd simply remove "hard", like we remove "obsc"
after someone cleans up a sequence in bad shape.
Doug
More information about the SeqFan
mailing list