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

北京大学学报（自然科学版）

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

刘田

北京大学计算机科学技术系，北京，100871

收稿日期:1999-02-12 出版日期:2000-01-20 发布日期:2000-01-20

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

LIU Tian

Department of Computer Science and Technology, Peking University, Beijing, 100871

Received:1999-02-12 Online:2000-01-20 Published:2000-01-20

摘要/Abstract

摘要： 定义与研究两族函数类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。

关键词: 结构复杂性, 函数类, 非确定性

Abstract: Two families of function classes C∙V and FC are defined and studied in this paper. These classes are defined by limiting the checking complexity of C∙V and the evaluating complexity of FC in C∈{P, UP, FewP, NP}, and by limiting the number of values of C∙V 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.