halpern%ibm-sj.csnet@csnet-relay.arpa (07/17/84)
From: Joe Halpern <halpern%ibm-sj.csnet@csnet-relay.arpa>
[Forwarded from the Halpern/IBM distribution by Laws@SRI-AI.]
The knowledge seminar continues on Friday, July 20, at 10 AM in Building
28 at IBM, with talks by Chris Cherniak and Tom Strat. I've appended the
abstracts below. This will be the second-to-last knowledge seminar for a
while. I'll give a seminar on logics of knowledge and complexity on
August 3. I've appended that abstract as well. I'm still open for
suggestions for more speakers if and when we start up again!
July 20
10 AM: COMPUTATIONAL COMPLEXITY AND PSYCHOLOGY -
Christopher Cherniak, Philosophy Department, University of Pennsylvania
What are the implications of computational complexity theory for
feasible knowledge representation and inference systems? One of the most
important current questions about complexity theory concerns its real
world relevance. For example, do the "hard" cases of a provably complex
problem occur frequently in the set of cases of the problem that are of
interest, or are the hard cases so enormous that no entity with
human-level resources would ever even encounter them? Some formal results
bear on this question, and some "empirical" studies of running times of
particular algorithms. I shall discuss another approach: Treating the
assumption that there is real world complexity as a working hypothesis,
and empirically testing some of its implications for human cognitive
psychology. I shall describe some of my experiments on people's use
of quick but dirty "prototypicality" deductive reasoning heuristics on
monadic predicate calculus problems.
11 AM: EVIDENTIAL REASONING AND ITS APPLICATION TO CONTINUOUS VARIABLES
Tom Strat - SRI International
Expert systems are often expected to draw conclusions based on
evidence about the world which is uncertain, inaccurate, and
incomplete. Such evidential information poses difficulties for
traditional theories for dealing with uncertain information. The
Shafer-Dempster approach, which is gathering an increasing amount of
interest, provides a suitable basis for representing and drawing
inferences from evidence.
The first half of the talk will be devoted to a review of
evidential reasoning as based on Shafer's work, including Dempster's
Rule of Combination for pooling multiple bodies of evidence to obtain
a consensus opinion. The second half will present some recent results
for dealing with continuous variables within the Shafer-Dempster
theory. A new representation will be introduced that provides strong
intuitions and visual interpretation of belief functions associated
with continuous variables. A number of examples will be included to
illustrate the concepts.
August 3, 1984, 10 AM.
LOGICS OF KNOWLEDGE AND COMPLEXITY THEORY
Joe Halpern, IBM San Jose
After a whirlwind review of complexity theoretic notions such as
NP-completeness, I will discuss the semantics for a modal logic
of knowledge and consider the complexity of the procedure for
deciding whether or not a formula is valid. It turns out if there
is only one player in the game, the problem is NP-complete. If
there are many players, the problem is PSPACE-complete; when
we add the notion of common knowledge, the problem becomes
exponential-time complete. This will be a two-hour,
self-contained presentation.