| 1 |
On Tue, 30 May 2017 09:22:45 +0100 |
| 2 |
Ciaran McCreesh <ciaran.mccreesh@××××××××××.com> wrote: |
| 3 |
|
| 4 |
> On Tue, 30 May 2017 09:42:45 +0200 |
| 5 |
> Alexis Ballier <aballier@g.o> wrote: |
| 6 |
> > Oh crap, this requires to solve SAT. |
| 7 |
> |
| 8 |
> The main problem would not be solving SAT, in this case. The problem |
| 9 |
> is providing the right answer when not enough information is given. |
| 10 |
> Spitting out a resolution which satisfies every dependency isn't |
| 11 |
> typically that difficult. Spitting out a resolution which doesn't |
| 12 |
> just turn off all your use flags and uninstall most of your programs |
| 13 |
> is the hard part. |
| 14 |
|
| 15 |
I don't really understand here: Assuming the formula is reduced where |
| 16 |
user-set useflags and profile-masked/forced ones are already assigned |
| 17 |
their true/false values, this leaves a formula with variables where |
| 18 |
changing any of those won't turn off (or on) anything you didn't want. |
| 19 |
If you can solve SAT on this reduced instance then you're safe, aren't |
| 20 |
you ? |
| 21 |
|
| 22 |
> > Not hard as in you need a Ph.D. in algorithms to solve it but the |
| 23 |
> > kind of hardness almost every cryptographic algorithm used today, |
| 24 |
> > and in the foreseeable future, relies on. |
| 25 |
> |
| 26 |
> Hrm, you're a bit off, there. SAT solving in practice isn't usually |
| 27 |
> that bad unless either your inputs are huge or they're deliberately |
| 28 |
> crafted to be ultra-nasty. Being NP-complete just means that instances |
| 29 |
> that will hit exponential behaviour exist, not that those instances |
| 30 |
> will occur in the application area you care about. |
| 31 |
|
| 32 |
Yes, SAT is somewhat one of the easiest NP complete problems. Still, |
| 33 |
do we accept everyone having php installed to have its 'emerge -uDN |
| 34 |
world' consume 1 cpu-minute? 10 cpu-minutes? 60 cpu-minutes? What's the |
| 35 |
limit? How do we define 'ultra-nasty' constructs? How do we avoid them? |
| 36 |
Do we want to spec the solver's heuristic used so that developers can |
| 37 |
rely on it performing well on some constructs and poorly on some others? |
| 38 |
Do we want to spec some syntax so that PM developers can use an |
| 39 |
heuristic performing well on the instances provided? |
| 40 |
|
| 41 |
I really believe that's too many questions for something that can be |
| 42 |
solved efficiently in a simpler manner. |
| 43 |
|
| 44 |
Bests, |
| 45 |
|
| 46 |
Alexis. |
Archives