COMPLEXITY RESULTS AND HEURISTIC METHODS FOR PROBABILISTIC LOGIC

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.

All items in National Archive of Phd theses are protected by copyright.

DOI
10.12681/eadd/0988
Handle URL
http://hdl.handle.net/10442/hedi/0988
ND
0988
Alternative title
ΠΟΛΥΠΛΟΚΟΤΗΤΑ ΚΑΙ ΕΥΡΕΤΙΚΕΣ ΜΕΘΟΔΟΙ ΓΙΑ ΤΗΝ ΠΙΘΑΝΟΤΙΚΗ ΛΟΓΙΚΗ
Author
Kavvadias, Dimitris (Father's name: J.)
Date
1988
Degree Grantor
University of Patras
Committee members
ΣΠΥΡΑΚΗΣ ΠΑΥΛΟΣ
ΚΥΡΟΥΣΗΣ ΕΛΕΥΘΕΡΙΟΣ
ΑΦΡΑΤΗ ΦΩΤΩ
ΜΑΡΙΤΣΑΣ ΔΗΜΗΤΡΗΣ
ΧΡΙΣΤΟΔΟΥΛΑΚΗΣ ΔΗΜΗΤΡΗΣ
Discipline
Natural Sciences
Computer and Information Sciences
Engineering and Technology
Electrical Engineering, Electronic Engineering, Information Engineering
Keywords
Algorithms; Artificial intelligence; Complexity; Expert systems; Heuristics; Linear programming; NP - completeness; PROBABILISTIC LOGIC
Country
Greece
Language
Greek
Description
116 σ.
Usage statistics
VIEWS
Concern the unique Ph.D. Thesis' views for the period 07/2018 - 07/2023.
Source: Google Analytics.
ONLINE READER
Concern the online reader's opening for the period 07/2018 - 07/2023.
Source: Google Analytics.
DOWNLOADS
Concern all downloads of this Ph.D. Thesis' digital file.
Source: National Archive of Ph.D. Theses.
USERS
Concern all registered users of National Archive of Ph.D. Theses who have interacted with this Ph.D. Thesis. Mostly, it concerns downloads.
Source: National Archive of Ph.D. Theses.
Related items (based on users' visits)