[seqfan] Re: easy and bref

[franktaw at netscape.net]

Don't forget the "more" keyword. In an ideal world, the sequences 
marked as "hard" under an expansive definition ought to be the same as 
the ones marked "more". In practice, there are sequences marked "more" 
that certainly are not hard.

I guess I would favor a middle ground. Which corresponds pretty well 
with what we have; with the usual share of misapplications, of course.

Franklin T. Adams-Watters

-----Original Message-----
From: Marc LeBrun <mlb at well.com>

>="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.



_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/