ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΚΑΙ ΕΥΡΕΤΙΚΕΣ ΜΕΘΟΔΟΙ ΓΙΑ ΤΗΝ ΠΙΘΑΝΟΤΙΚΗ ΛΟΓΙΚΗ

Abstract

THE DESIGN OF EXPERT SYSTEMS POSES A PROBLEM KNOWN AS "APPROXIMATE REASONING". IN THIS PROBLEM WE ARE ASKED TO DETERMINE THE BELIEF TO ANOTHER STATEMENT. BASED ON THE THEORY OF "PROBABILISTIC LOGIC", WE MODEL UNCERTAINTY AS PROBABILITY OF STATEMENTS. A SET OF STATEMENTS CAN BE MODELLED AS A LINEAR PROGRAM, WHILE THE BASIC PROBLEM IS PROVED POLYNOMIALLY EQUIVALENT TO "PROBABILISTIC SATISFIABILITY". WE NEXT SHOW THAT EVEN THE SIMPLEST FORMS OF "PROBABILISTIC LOGIC" ARE COMPUTATIONALLY INTRACTABLE (NP-COMPLETE) AND WE PROPOSE VARIOUS HEURISTICS BASEDON THE SIMPLEX METHOD FOR THE PRACTICAL SOLUTION OF THE PROBLEM.

Η ΣΧΕΔΙΑΣΗ ΣΥΣΤΗΜΑΤΩΝ ΕΜΠΕΙΡΟΓΝΩΜΟΝΩΝ ΘΕΤΕΙ ΕΝΑ ΠΡΟΒΛΗΜΑ ΓΝΩΣΤΟ ΣΑΝ "ΠΡΟΣΕΓΓΙΣΤΙΚΗ ΕΞΑΓΩΓΗ ΣΥΜΠΕΡΑΣΜΑΤΩΝ". ΣΤΟ ΠΡΟΒΛΗΜΑ ΑΥΤΟ ΤΑ ΔΕΔΟΜΕΝΑ ΕΙΝΑΙ ΠΡΟΤΑΣΕΙΣ ΕΛΛΙΠΕΙΣ ΚΑΙ ΑΛΛΗΛΟΣΥΓΚΡΟΥΟΜΕΝΕΣ ΚΑΙ Ο ΣΚΟΠΟΣ ΕΙΝΑΙ ΝΑ ΒΡΕΘΕΙ Η ΕΜΠΙΣΤΟΣΥΝΗ ΣΕ ΜΙΑ ΑΛΛΗ ΠΡΟΤΑΣΗ. ΜΕ ΒΑΣΗ ΤΗΝ ΘΕΩΡΙΑ ΤΗΣ ΠΙΘΑΝΟΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΜΟΝΤΕΛΟΠΟΙΟΥΜΕ ΤΗΝ ΑΒΕΒΑΙΟΤΗΤΑ ΣΑΝ ΠΙΘΑΝΟΤΗΤΑ. ΕΝΑ ΣΥΝΟΛΟ ΠΡΟΤΑΣΕΩΝ ΜΟΝΤΕΛΟΠΟΙΕΙΤΑΙ ΣΑΝ ΕΝΑ ΓΡΑΜΜΙΚΟ ΠΡΟΓΡΑΜΜΑ ΤΟ ΔΕ ΒΑΣΙΚΟ ΠΡΟΒΛΗΜΑ ΑΠΟΔΕΙΚΝΥΕΤΑΙ ΠΟΛΥΩΝΥΜΙΚΟ ΙΣΟΔΥΝΑΜΟ ΜΕ ΤΗΝ "ΠΙΘΑΝΟΤΙΚΗ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ". ΣΤΗΝ ΣΥΝΕΧΕΙΑ ΔΕΙΧΝΟΥΜΕ ΟΤΙ ΚΑΙ ΟΙ ΑΠΛΟΥΣΤΕΡΕΣ ΜΟΡΦΕΣ ΤΗΣ ΠΙΘΑΝΟΤΙΚΗΣ ΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑΣ ΕΙΝΑΙ ΥΠΟΛΟΓΙΣΤΙΚΑ ΔΥΣΚΟΛΕΣ. (ΝΡ-ΠΛΗΡΕΙΣ)ΚΑΙ ΠΡΟΤΕΙΝΟΥΜΕ ΔΙΑΦΟΡΕΣ ΕΥΡΕΤΙΚΕΣ ΜΕΘΟΔΟΥΣ ΠΟΥ ΒΑΣΙΖΟΝΤΑΙ ΣΤΗΝ ΜΕΘΟΔΟ SIMPLEXΓΙΑ ΤΗΝ ΠΡΑΚΤΙΚΗ ΛΥΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣ.