Storage space versus validity of answers in probabilistic question-answering systems

The trade-offs between the required storage space and the validity of answers produced by probabilistic question-answering (PQA) systems are studies. If the correct answer to a given query is "yes" and the system, instead, issues the estimate that the query has a probability of being true, then the economic loss to the user can be measured by a distortion function that decreases monotonically with . A system will be called elastic if a drastic memory saving may be achieved by tolerating a small level of average distortion. The main result reported is that for a large class of distortion measures (i.e., measures exceeding with , if a binary QA system (true-false answers) is inelastic then the corresponding probabilistic QA system must also be inelastic. This result implies, for example, that a PQA system that is designed to answer all binary questions on an arbitrary dataset is inelastic. Similarly a PQA system admitting singly conjunctive questions such as "Are both and in the dataset?" is also inelastic.