[seqfan] Re: easy and bref

[Marc LeBrun]

>="D. S. McNeil" <dsm054 at gmail.com>
> I guess I don't see "hard" as a permanent property but as a
> description of our state of knowledge... 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.

>="franktaw at netscape.net" <franktaw at netscape.net>
> 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.

>="Charles Greathouse" <charles.greathouse at case.edu>
> That's a pretty hefty requirement; I don't think we should limit hard
> to just such cases.
> ...
> But I think I agree that it would be best to use it only when the
> problem is known (in some sense) to be hard.

Heh.  I surely agree with some of this, but deciding in which sense is hard.


I propose that we continue to interpret a bare "hard" keyword to signify
Not-Known-to-be-Easy, AND, for the rare Known-to-be-Difficult cases,
recommend it be supplemented with comments or references documenting that
verdict.


Certainly "hard" should be used if the sequence is known to be hard in some
technical sense.  Of course if this is known then it's reasonable to ask for
this knowledge to be shared via comments, references or the like.

However I also think it's constructive to simply tag something as "hard" if
the submitter, after making some reasonable amount of sincere effort, is
unable to come up with anything significantly better than some brutish
calculation.

For one thing this might wave a red flag in front of someone with better
power tools, motivating them to gain eternal glory by adding more terms to
the OEIS and clearing the "hard" keyword!


For example one of the first sequences I ever sent Neil is A006585.  I
obtained up to a(7) by turning an old 286 into a space-heater, and John
Dethridge has only extended it to a(8) in 2004.  I think the "hard" keyword
seems at least provisionally plausible simply by the test of time.  But I
haven't the slightest clue how to even begin proving that it is hard, in any
technical sense (eg some Conway-Egyptian-Fractran machine equivalence?)

On the other hand, for a long time I've personally suspected that A094206
might be hard in some technical sense, but haven't set the flag because of
lingering fantasies that some unidentified future expert in some field I
don't even know the name of might someday be able to easily extend it.

Which approach do you think is the most likely to spur progress--the
provocative or the timid?  I'd rather risk having some false "hards" turn
out to be stimulating challenges, than reserve "hard" only for a rarely-used
and tough-to-justify "do not enter--further progress is hopeless" sign.