On Checking versus Evaluation of Multiple Queries

The plausibility of computing the answers to many membership queries to a hard set with few queries is the subject of the theory of terseness. In this paper, we develop companion theories-both complexity-theoretic and recursion-theoretic-of characteristic vector terseness. These theories ask whether the answers to many membership queries to a hard set can be checked with fewer queries.

Authors

• W.I. Gasarch
• L.A. Hemachandra
• A. Hoene

Keywords

No keywords are indexed for this paper.