Random Verification of Knowledge-based Systems with Uncertainty

Contents

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.