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.
>
> 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 :-/
Can you formalise what you look for?
Perhaps this can be sped up, e.g. by doing
some ILP or something like this?
You can also think of your "NO sets" as a set of SAT clauses of the form
!x_{i_1} || !x_{i_2} || ... || !x_{i_m},
and all of them should hold true.
So you want to find all "maximal length" solutions to this SAT problem.
Perhaps some SAT solvers can do this, I don't know
(by the way, SAT solvers is an area where people do care a lot about actual fast
implementations)
Dima
>
>> 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.
