On 2014-09-13, Nathann Cohen <[email protected]> wrote:
> 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.
this is only one of the current trends - other ones argue that algorithms
should be accompanied by implementations, and then there is a lot of things done
on polynomial-time algorithms.
(of course if you look for an excuse not to check literature, you can have one,
always :-))
Anyhow, one speedup can come from your function being invariant under some
permutations of variables; perhaps you can check this quickly.
>
> 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.
