On pią, 2017-06-02 at 14:16 +0200, Alexis Ballier wrote:
> On Thu, 01 Jun 2017 23:31:25 +0200
> Michał Górny <mgorny@gentoo.org> wrote:
> > My current code is on github [1]. It's ugly, slow and incomplete. It's
> > merely a proof-of-concept and testing toy but still could give some
> > clues.
> > 
> > [1]:https://github.com/mgorny/required-use
> 
> 
> Nice work by the way. I've not looked much at the code but I've tried
> it on a few examples and it worked well. Then I tried on the php
> example and it didn't finish within 30 mins so I stopped it.
> 
> I think we should really try to find a sub-exponential solution to
> this, I doubt there's anything that can be done if the only solution is
> to enumerate all the possibilities.

Well, as I said, you can split it into multiple independent groups
(that's what I did). Then you solve each of them independently. However,
that was done purely for research needs and I'm not sure how useful it's
going to be in practice.

I can imagine something like:

  || ( foo_* )

for 30-40 flag USE_EXPAND being a problem -- while a trivial constraint
to verify. So the 2^n solution I'd rather consider a nice way to test
the algorithm rather than something potentially useful for verification.

-- 
Best regards,
Michał Górny