| 1 |
On Mon, 29 May 2017 23:23:55 +0200 |
| 2 |
Michał Górny <mgorny@g.o> wrote: |
| 3 |
> > Can you provide an efficient algorithm for the above syntax? |
| 4 |
> > That is, given a set of +/- useflags forced by user, output the set |
| 5 |
> > of effective useflags (or a rant if it is inconsistent). |
| 6 |
> |
| 7 |
> I'd rather leave that to people who are good with algorithms. I find |
| 8 |
> the whole thing scary but I don't really see a sane alternative here. |
| 9 |
> Worst case, we have to figure out some arbitrary limitations to keep |
| 10 |
> things sane. |
| 11 |
|
| 12 |
That bit is NP-complete by an easy reduction from SAT. That isn't |
| 13 |
necessarily a problem, because resolution isn't even in NP yet we're |
| 14 |
still managing to spit out decent answers most of the time. Rather, the |
| 15 |
difficulty lies in spitting out a *good* solution to the problem from |
| 16 |
a user's perspective, and that's something that can't be done without |
| 17 |
extremely high quality inputs. |
| 18 |
|
| 19 |
-- |
| 20 |
Ciaran McCreesh |
Archives