关于函数的验证复杂性、求值复杂性和输出值个数

定义与研究两族函数类C·V和FC。定义这些类的方法是限制C·V的验证复杂性和FC 的求值复杂性在C∈{P, UP, FewP, NP｝之内，并且限制C·V的输出值个数在V ∈{SV, PV, MV｝之内。这些类之间的包含与相等关系以及在函数复合运算下的封闭性质被完全确定。这些类不仅统一了过去已知的函数类而且定义了新的函数类，例如FewP·PV. FewP·PV是自然对应于FewP的函数类，因为FewP·PV的定义域与验证复杂性和求值复杂性恰好都是FewP。

On Checking Complexity, Evaluating Complexity and Number of Values for Functions

Two families of function classes . and FC are defined and studied in this paper.These classes are defined by limiting the checking complexity of . and the evaluating complexity of FC in ∈{P,UP,FewP,NP},and by limiting the number of values of . in V∈{SV,PV,MV}. The inclusion and equality relations and the closure properties under function composition operator among these classes are completely decided.These classes not only unify previously known classes of functions but also define new function classes such as Few P.PV which is a natural function analogue of Few P in that both the domain and checking and evaluating complexity of Few P.PV are exactly in FewP.