more challenge sequences needed
Rainer Rosenthal
r.rosenthal at web.de
Wed May 25 18:56:20 CEST 2005
> ... or the Golomb ruler problem would be perfect,
> but these have already been used.
Hello Neil,
this is far too great a chance for extending my
favourite A004137 to let it go without fight :-)
The rulers considered here are *not* the Golomb
rulers, for which there is indeed a vast literature
and extensive search by globally connected people.
There is just ONE really clever type of rulers,
which probably will be optimal for the next may
be 10 or 15 arguments: the type invented by Wich-
mann in the 1960's.
Computational evidence was quite poor before Peter
Luschny did focus on this sequence.
We weren't able to prove the validity of any method
for reducing the search tree. It would be of great
value to have solid knowledge about further members
of this sequence, so that theoretical considerations
could be proved or disproved more easily.
> Here are the constraints on the problem:
>
> 1) It must be NP-complete
Nobody has proved the opposite.
> 2) It must be simple to describe
Find 1 = x_1 < x_2 < ... < x_n = L such that
the differences x_i - x_j don't have holes
and such that L is maximal.
> 3) It should not have been widely explored
I think they should try something, which people
are interested in. Otherwise their effort will
make nobody happy. And *if* they try something
interesting, then surely there *must* have been
some exploration done before. The term "widely
explored" is widely flexible ;-)
> 4) A solution must be easy to check (= it
> doesn't require a lot of computation to check)
This may be the killer argument: a solution is
proved to be one, if there is no solution for
L+1. And to prove that, you will need very much
time :-(
(While on the other hand it is easy to show that
such a set {x1,...x_m} doesn't have holes in its
differences.)
> 5) It has to be computed from N=8 to at most 64
Hmmm... no comment.
Still hoping for the election, and thank you very
much for your first friendly welcome to that
suggestion of mine,
best regards,
Rainer Rosenthal
r.rosenthal at web.de
More information about the SeqFan
mailing list