Random Verification of Knowledge-based Systems with Uncertainty

Michel de Rougement

We describe a new formal method to verify knowledge-based systems dealing with uncertain data following a probabilistic model. For a large class of uncertainty models, it is a hard combinatorial problem (PSPACE) to verify that the probability of correctness is greater than k. We present a method, based on the interactive proof systems, that allows a random verifier to check a prover in O(n2). We then show how to use it in practice to rate Knowledge-Based systems.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.