Re: RFC: implementation of package pools
Anthony Towns wrote:
>
> *sigh* Please pay attention rather than trying to be smart. New packages
> (genuinely new ones, that haven't been in the archive ever before) are
> checked for various common sense problems and licensing issues before
> being added. If you can automate this in an accurate manner, please,
> go ahead. Until that time, it'll stay by hand, exactly as is desired.
>
Checking the license is AI-complete. ;) I've written a proposal about
this but will put it together with my other ideas about testing
and post as an RFC since this thread's gone too offtopic.
> > [notation: ! is negation, /\ conjunction, \/ disjunction ]
> > P /\ Q /\ !R .... /\ Z
> > (I know you don't like my ASCII art, but no logic symbols on the keyboard)
>
> Logic symbols are a solved problem: &, |, ~.
>
Okay, next time we can use prolog syntax ;)
> a Depends: b | c, d translates to (~a | b | c) & (~a | d)
> a Conflicts: b, c translates to (~a | ~b) & (~a | ~c)
>
> a is installable translates to "a"
>
Well, there must be something wrong here since if I give a valuation 0
to a then the two propositional sentences are satisfied trivially. Could you
please review this? Let's not be mistaken.
> > In many other cases we have simple conjunctive forms of the sort
> > (P \/ Q) /\ (S \/ !T) /\ X
> ^^^^^^
> We never come across a clause that looks like that, for example.
I think we do. If you'd like let's discuss it after you review
your formalization.
>
> > in which there's little or no overlap of propositional symbols among
> > conjunctions. [makes the instance quite easy to solve]
>
> I'm not sure that's true. You'd have to do some investigation to work
> it out.
>
In most of the depends, conflicts I find it very trivial to satisfy
the conditions by inspection. This would be the case for programs, too.
> > and correct me if I'm wrong, but the propositional sentences are
> > unrestricted CNF (conjunctive normal form), so it really is SAT.
>
> See above. It's equivalent, and very close, but it's not exactly the same.
Well, either they are exactly translatable or not. If not, it's not SAT,
and the problem would be a relaxed SAT which would be easier (perhaps
even become solvable in P)
> > I see. Most of the sentences are easy instances anyway.
>
> That might be what you'd expect (and it's what I'd expect), but it's not
> been proven or investigated.
So, I think this is what we should do. Let's continue discussing this
and clear any remaining confusion.
Thanks,
--
Eray (exa) Ozkural
Comp. Sci. Dept., Bilkent University, Ankara
e-mail: erayo@cs.bilkent.edu.tr
www: http://www.cs.bilkent.edu.tr/~erayo
Reply to: