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.
![]() | |
![]() | Download full text in PDF format (5.68 MB)
(Available only to registered users)
|
All items in National Archive of Phd theses are protected by copyright.
|
Usage statistics

VIEWS
Concern the unique Ph.D. Thesis' views for the period 07/2018 - 07/2023.
Source: Google Analytics.
Source: Google Analytics.

ONLINE READER
Concern the online reader's opening for the period 07/2018 - 07/2023.
Source: Google Analytics.
Source: Google Analytics.

DOWNLOADS
Concern all downloads of this Ph.D. Thesis' digital file.
Source: National Archive of Ph.D. Theses.
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.
Source: National Archive of Ph.D. Theses.