A general framework is presente for the study of complexity classes that are defined via polynomial time algorthms that compute partial information about the characteristic function of a given input Given n implied by IN and a family D of sets D {0,1}~*, a language A is polynomially D-verbose (or: A implied by P [D]) iff there is a polynomial time algorithm that on input (x_1,...x_n) outputs a D implied by D such that the characteristic string X_A (X_1,...,X_n) is in D. Also the variant where only pairwise distinct input words are allowed is studied. p-selective sets, p-verbose sets, easily p-countable sets, sets that allow a polynomial time frequency computation, and cheatable sets are special cases of this definition.
展开▼
