Yoooooooooo !
> Sounds like an interesting problem, do you know of an efficient algorithm
to do this (without simply trying all sets of course)? Have you looked in
the literature?
I don't believe in "literature" anymore. I don't know a lot about other
fields of research, but in graph theory people who say that they work on
'algorithms' apparently never heard of what a data structure is. All they
care about is asymptotic complexity and whether their problem is
polynomial/NP-Hard, especially on unheard-of classes of INPUT.
What my implementation does is rather simple:
1) Think of all subsets of X, and say that the (unique) "predecessor" of a
set S is S-{max(S)}. This is a graph.
2) Start from the empty set, and do a breadth-first search from there (this
will explore all sets of size 1, then size 2, then [...])
3) For each set S that you explore, decide whether the set S already
contains a set S' for which f(S') is False. In this case you know that f(S)
is wrong without even calling S. If there is no such set then compute f(S).
If it is true store the set somewhere, if it is wrong stop the exploration
and keep this set S in the database of "NO" answers.
The good thing here is that it is rather "quick" to test whether your
current set S contains a set for which f was False. Just store all your
"NO" sets in a binary matrix (i.e. an array of bitsets in Sage), and all
you need to do to run the test is compute the intersection of some bitsets.
There is no magic in the algorithm and it is 25 lines long. It is just a
good way to avoid calling f too often when this function is very slow.
Unfortunately it has been running for 10 hours on my computer and I still
did not find the set I am looking for :-/
> I have a "coding theory" feel about this problem because it sounds a bit
like finding the minimal-weight vectors for a code (the sets X
corresponding to the index sets of zero coefficients)
NOooooooo idea about that O_o
Nathann
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
