On Mon, Oct 23, 2000 at 08:36:46PM +0300, Eray Ozkural wrote:
> Anthony Towns wrote:
> > On Mon, Oct 23, 2000 at 07:09:08AM +0300, Eray Ozkural wrote:
> > > No, I'm saying "does it support automatic upload and removal?"
> > Exactly to the extent that's desired, yes it does. As discussed in the
> > second last mail of mine in this thread.
> Excellent. Then people surely won't wait for 1 or 2 weeks before their
> new packages appear in the archive.
*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.
> > > it. You could at least tell me about the algorithm that you used;
> > > did you do random-restart hill climbing, or do you resort to a heuristics?
> > The first thing you'll need to note is that it's *not* the SAT
> > problem. There's a trivial "installable" situation that satisfies all the
> > "givens": don't try to install anything. Once you install one thing, that
> > invalidates a bunch of other statements, which it then tries to correct.
> Yeah, I noticed that. Also in many cases it seemed to me that the
> sentence becomes something simple like
> [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: &, |, ~.
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"
If you assume nothing need be installable, you get a set of statements
where just setting all terms to false satisfies every clause.
Once you say something must be installable though, things become more
complicated.
It's possible to rewrite any SAT problem in the form of Depends/Conflicts
statements and a single "install this" term, with linear extra terms
and statements.
> 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.
> 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.
> 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.
> Yea, I think you're using some stack of list-of-unexpanded notes.
> When such things are done iteratively, it becomes a bit confusing
> for a reviewer.
It's somewhat recursive (dependencies form a tree, after all), but it
has a look ahead which cuts across branches. I don't see any way of
doing it recursively in as convenient a manner.
> I personally don't understand iterative backtracking
> code I wrote some time ago. :) The preprocessor macros make it harder
> to read, too. :) I now have some trust in optimizing compilers, and simply
> write anything recursive really recursive.
Oh, yes, I see what you mean by the preprocessor macros. I was halfway
through changing that structure to be somewhat different (an array,
not a list, iirc), but didn't finish it. But they're simply ugly, they're
not particularly complicated.
> 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.
Cheers,
aj
--
Anthony Towns <aj@humbug.org.au> <http://azure.humbug.org.au/~aj/>
I don't speak for anyone save myself. GPG signed mail preferred.
``We reject: kings, presidents, and voting.
We believe in: rough consensus and working code.''
-- Dave Clark
Attachment:
pgpfZaN1IQomw.pgp
Description: PGP signature