| 1 |
On Tue, 30 May 2017 09:42:45 +0200 |
| 2 |
Alexis Ballier <aballier@g.o> wrote: |
| 3 |
> Oh crap, this requires to solve SAT. |
| 4 |
|
| 5 |
The main problem would not be solving SAT, in this case. The problem is |
| 6 |
providing the right answer when not enough information is given. |
| 7 |
Spitting out a resolution which satisfies every dependency isn't |
| 8 |
typically that difficult. Spitting out a resolution which doesn't |
| 9 |
just turn off all your use flags and uninstall most of your programs is |
| 10 |
the hard part. |
| 11 |
|
| 12 |
> Not hard as in you need a Ph.D. in algorithms to solve it but the |
| 13 |
> kind of hardness almost every cryptographic algorithm used today, and |
| 14 |
> in the foreseeable future, relies on. |
| 15 |
|
| 16 |
Hrm, you're a bit off, there. SAT solving in practice isn't usually |
| 17 |
that bad unless either your inputs are huge or they're deliberately |
| 18 |
crafted to be ultra-nasty. Being NP-complete just means that instances |
| 19 |
that will hit exponential behaviour exist, not that those instances |
| 20 |
will occur in the application area you care about. |
| 21 |
|
| 22 |
-- |
| 23 |
Ciaran McCreesh |
Archives