Recognition Problem
For a query q we will define the recognition problem as follows:
Given an instance I and a tuple u, determine whether u belongs to the answer q(I).
Or formaly:
{enca(I)#enca (u) | u Î q(I), a an enumeration of adom(I)}
The complexity of q is the complexity of its recognition time.
For each spcae complexity class C (where C stands for P, NP etc.), we can define a corresponding complexity class of queries, denoted by QC. The class of queries consist of all queries whose recognition problem is in C.
Example: the class QP consist of all queries for which the recognition problem is in P.
Another option: define the complexity of queries based on the complexity of actually constructing the result of the query.
In most cases the definitions are interchangeable. In particular, for complexity classes insensitive to a polynomial factor the definitions are equivalent.
In General, the definition based on constructing the result distinguish between a query with a large answer and a one with a small answer, but may not distinguish between easy and hard queries with large results.
We will use the definition of query complexity based on the recognition problem.